An information statistics approach to data stream and communication complexity

By Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar. 2002

692 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Geometric Lower Bounds for Distributed Parameter Estimation Under Communication Constraints (2018, neutral): “Due to the independence of X1, · · · ,Xn, we have the following lemma which is similar to the “cut-paste” property Bar-Yossef et al. (2004) for the blackboard communication protocol: Lemma 9 The distribution of the transcript Y can be written as follows: for any y ∈ {0, 1}nk , we have PX1,··· ,Xn∼P…”
Communication lower bounds for statistical estimation problems via a distributed data processing inequality (2015, methodology): “Then the squared Hellinger distance is within a constant factor of I( V ; Π) (see Lemma 10, and the lower bound side was proved by [BYJKS04]), Therefore, in the unbiased case, (2) implies the typical form of the data processing inequality.”
On Communication Cost of Distributed Statistical Estimation and Dimensionality (2014, methodology): “There has been a lot of work on the paradigm of studying communication complexity via the notion of information complexity [6, 7, 8, 9, 10].”
Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation (2013, background): “The inherent limitations of streaming and distributed algorithms, including memory and communication constraints, have been extensively studied within theoretical computer science (e.g. [4, 11, 23, 44, 12]).”
Lower Bounds in Differential Privacy (2011, background): “In fact, as [13] was dealing with 2-party protocols, the connection was actually between differentially private protocols and that of information content [1, 2] which is a symmetric variant of mutual information useful in 2-party protocols.”
Distributed low rank approximation of implicit functions of a matrix (2016, methodology): “We prove it by reduction from the L∞ problem [23].”
The Limits of Two-Party Differential Privacy (2010, neutral): “, the inner product function [14], we get the desired result.”
Data streams: algorithms and applications (2005, methodology): “An information-based approach to data stream lower bounds i s in [103].”
Tight bounds for distributed functional monitoring (2011, methodology): “The previous best lower bound is̃Ω(N1−2/pε−2/p) [8] in FOCS, 2002, and no progress has been made since then.”
Distributed Statistical Estimation of High-Dimensional and Nonparametric Distributions (2018, background): “Due to the independence of X1, · · · , Xn, we have the following lemma which is similar to the “cut-paste" property [13] for the blackboard communication protocol:”
Optimal approximations of the frequency moments of data streams (2005, background): “space lower bound [13, 2] for this problem, our algorithm is essentially optimal.”
Unified lower bounds for interactive high-dimensional estimation under information constraints (2020, methodology): “In order to bound the resulting terms of the sum, we will rely on the so-called cut-paste property of Hellinger distance [6].”
Optimality guarantees for distributed statistical estimation (2014, background): “More recent work studies randomization and introduces information-theoretic measures for communication complexity [9, 4, 5], where the problem is to guarantee that θ ( x, y ) is computed correctly with high probability under a given (known) distribution P on x and y .”
Principal Component Analysis and Higher Correlations for Distributed Data (2013, background): “Known lower bounds for this problem from that literature rule out low communication algorithms when k > 2 in the distributed setting when the number of servers grows as a power of n ([9, 12, 18]), or when there are only two servers and the entries are allowed to be negative [9].”