We introduce VoiceFilter-Lite, a single-channel source separation model that runs on the device to preserve only the speech signals from a target user, as part of a streaming speech recognition system.Delivering such a model presents numerous challenges: It should improve the performance when the input signal consists of overlapped speech, and must not hurt the speech recognition performance under all other acoustic conditions.Besides, this model must be tiny, fast, and perform inference in a streaming fashion, in order to have minimal impact on CPU, memory, battery and latency.We propose novel techniques to meet these multi-faceted requirements, including using a new asymmetric loss, and adopting adaptive runtime suppression strength.We also show that such a model can be quantized as a 8-bit integer model and run in realtime.

Let u, v ∈ R+Ωbe positive unit vectors and S ∈ R+Ω×Ωbe a symmetric substochastic matrix. For an integer t ≥ 0, let mt= 〈 v, Stu〉, which we view as the heat measured by v after an initial heat configuration u is let to diffuse for t time steps according to S. Since S is entropy improving, one may intuit that mtshould not change too rapidly over time. We give the following formalizations of this intuition. We prove that mt+2≥ mt1+2/t, an inequality studied earlier by Blakley and Dixon (also Erdos and Simonovits) for u=v and shown true under the restriction mt≥ e-4t. Moreover we prove that for any ε>0, a stronger inequality mt+2≥ t1-ε· mt1+2/tholds unless mt+2mt-2≥ δmt2for some δ that depends on ε only. Phrased differently, ∀ε > 0, ∃δ > 0 such that ∀S, u, v mt+2/mt1+2/t≥ min{t1-ε, δmt1-2/t/mt-2}, ∀t ≥ 2, which can be viewed as a truncated log-convexity statement. Using this inequality, we answer two related open questions in complexity theory: Any property tester for k-linearity requires Ω(klog k). queries and the randomized communication complexity of the k-Hamming distance problem is Ω(k log k). Further we show that any randomized parity decision tree computing k-Hamming weight has size exp(Ω(k log k)).

In this paper we study the two player randomized communication complexity of the sparse set disjointness and the exists-equal problems and give matching lower and upper bounds (up to constant factors) for any number of rounds for both of these problems. In the sparse set disjointness problem, each player receives a k-subset of [m] and the goal is to determine whether the sets intersect. For this problem, we give a protocol that communicates a total of O(k log(r)k) bits over r rounds and errs with very small probability. Here we can take r = log* k to obtain a O(k) total communication log* k-round protocol with exponentially small error probability, improving on the O(k)-bits O(log k)-round constant error probability protocol of Hastad and Wigderson from 1997. In the exists-equal problem, the players receive vectors x, y ∈ [t]nand the goal is to determine whether there exists a coordinate i such that xi= yi. Namely, the exists-equal problem is the OR of n equality problems. Observe that exists-equal is an instance of sparse set disjointness with k = n, hence the protocol above applies here as well, giving an O(n log(r)n) upper bound. Our main technical contribution in this paper is a matching lower bound: we show that when t = Ω(n), any r-round randomized protocol for the exists-equal problem with error probability at most 1/3 should have a message of size Ω(n log(r)n). Our lower bound holds even for super-constant r ≤ log* n, showing that any O(n) bits exists-equal protocol should have log* n - O(1) rounds. Note that the protocol we give errs only with less than polynomially small probability and provides guarantees on the total communication for the harder set disjointness problem, whereas our lower bound holds even for constant error probability protocols and for the easier exists-equal problem with guarantees on the max-communication. Hence our upper and lower bounds match in a strong sense. Our lower bound on the constant round protocols for exist-sequal shows that solving the OR of n instances of the equality problems requires strictly more than n times the cost of a single instance. To our knowledge this is the first example of such a super-linear increase in complexity.

In this paper, we present near-optimal space bounds for Lp-samplers. Given a stream of updates (additions and subtraction) to the coordinates of an underlying vector x in Rn, a perfect Lp sampler outputs the i-th coordinate with probability xipxpp. In SODA 2010, Monemizadeh and Woodruff showed polylog space upper bounds for approximate Lp-samplers and demonstrated various applications of them. Very recently, Andoni, Krauthgamer and Onak improved the upper bounds and gave a O(ε-plog3n) space ε relative error and constant failure rate Lp-sampler for p є [1,2]. In this work, we give another such algorithm requiring only O(ε-plog2n) space for p є (1,2). For p є (0,1), our space bound is O(ε-1log2n), while for the p=1 case we have an O(log(1/ε)ε-log2n) space algorithm. We also give a O(log2n) bits zero relative error L0-sampler, improving the O(log3n) bits algorithm due to Frahling, Indyk and Sohler.