Search

A streaming algorithm is said to be adversarially robust if its accuracy guarantees are maintained even when the data stream is chosen maliciously, by an adaptive adversary . We establish a connection between adversarial robustness of streaming algorithms and the notion of differential privacy . This connection allows us to design new adversarially robust streaming algorithms that outperform the current state-of-the-art constructions for many interesting regimes of parameters.

Automatic speech recognition (ASR) systems have dramatically improved over the last few years. ASR systems are most often trained from 'typical' speech, which means that underrepresented groups don't experience the same level of improvement. In this paper, we present and evaluate finetuning techniques to improve ASR for users with non-standard speech. We focus on two types of non-standard speech: speech from people with amyotrophic lateral sclerosis (ALS) and accented speech. We train personalized models that achieve 62% and 35% relative WER improvement on these two groups, bringing the absolute WER for ALS speakers, on a test set of message bank phrases, down to 10% for mild dysarthria and 20% for more serious dysarthria. We show that 71% of the improvement comes from only 5 minutes of training data. Finetuning a particular subset of layers (with many fewer parameters) often gives better results than finetuning the entire model. This is the first step towards building state of the art ASR models for dysarthric speech., Comment: 5 pages

We consider the class of valuations on indivisible items called gross-substitute (GS). This class was introduced by Kelso and Crawford (1982) and is widely used in studies of markets with indivisibilities. GS is a condition on the demand-flow in a specific scenario: some items become more expensive while other items retain their price. We prove that GS implies a much stronger condition, describing the demand-flow in the general scenario in which all prices may change. We prove that the demand of GS agents always flows (weakly) downwards, i.e, from items with higher price-increase to items with lower price-increase. We show that this property is equivalent to GS and is not true when there are complementarities., Comment: 7 pages. Improved examples and added missing proofs

The "law of one price" asserts that homogeneous goods must sell for the same price across locations and vendors. While many deviations from this 'law' have been observed in the real world, it remains a useful building block in economic theory, and serves as a benchmark for empirical studies. A crucial underlying assumption used in arguing for the validity of the law is the homogeneity of goods and buyers: buyers do not care which of the goods they buy, or which seller they are buying it from, nor do sellers care about the identity of the buyers. In other words, any two instances of the good are perfect substitutes for the buyers, as are any two buyers from any seller's point of view. This paper makes the formal claim that even in the presence of heterogeneous preferences, an approximate version of the law remains valid, and the approximation improves as the market grows large. To prove this result we use the assignment game model of Shapley and Shubik (1971) in which there is a finite set of firms and a finite set of workers, and each firm is looking to hire exactly one worker in exchange for a negotiable salary. Each firm has a (possibly different) value for hiring each of the workers, and each worker has a (possibly different) reservation value for working for each of the firms, and utilities are assumed to be linear in money. We study three different random models which generate the value: In the independent and bounded model, we assume that this productivity is separable in the firm's quality, the worker's human capital level, and an idiosyncratic component that is independently and identically distributed according to some bounded distribution.

We give a quantum algorithm for evaluating a class of boolean formulas (such as NAND trees and 3-majority trees) on a restricted set of inputs. Due to the structure of the allowed inputs, our algorithm can evaluate a depth $n$ tree using $O(n^{2+\log\omega})$ queries, where $\omega$ is independent of $n$ and depends only on the type of subformulas within the tree. We also prove a classical lower bound of $n^{\Omega(\log\log n)}$ queries, thus showing a (small) super-polynomial speed-up., Comment: 30 pages, 2 figures, v3: clarified exposition, matches journal reference

arxiv only, Quantum money is a cryptographic protocol in which a mint can produce a quantum state, no one else can copy the state, and anyone (with a quantum computer) can verify that the state came from the mint. We present a concrete quantum money scheme based on superpositions of diagrams that encode oriented links with the same Alexander polynomial. We expect our scheme to be secure against computationally bounded adversaries., United States. Dept. of Energy (DE-FG02-94ER40818), W. M. Keck Foundation Center for Extreme Quantum Information Theory, U.S. Army Research Laboratory (ARO grant number W911NF-09-1-0438), National Science Foundation (U.S.) (grant number CCF-0829421), National Defense Science and Engineering Graduate Fellowship, Natural Sciences and Engineering Research Council of Canada, Microsoft Research

We provide a simple example that illustrates the advantage of adaptive over non-adaptive strategies for quantum channel discrimination. In particular, we give a pair of entanglement-breaking channels that can be perfectly discriminated by means of an adaptive strategy that requires just two channel evaluations, but for which no non-adaptive strategy can give a perfect discrimination using any finite number of channel evaluations., Comment: 11 pages