Fetching the paper…
Reading the bibliography…
We prove an optimal $\Omega(n)$ lower bound on the randomized communication complexity of the much-studied Gap-Hamming-Distance problem.
Typical distributions of linear functionals in finite-dimensional spaces of high dimension
V. N. Sudakov · 1978
Earlier work this paper cites.
Asymptotics of graphical projection pursuit
P. Diaconis and D. Freedman · 1984
Earlier work this paper cites.
Geometric bounds on the Ornstein-Uhlenbeck velocity process
C. Borell · 1985
Earlier work this paper cites.
Monotone circuits for connectivity require super-logarithmic depth
M. Karchmer and A. Wigderson · 1988
Earlier work this paper cites.
Entropy and Information Theory
R. M. Gray · 1990
Earlier work this paper cites.
On the distributional complexity of disjointness
A. Razborov · 1990
Earlier work this paper cites.
On data structures and asymmetric communication complexity
P. B. Miltersen, N. Nisan, S. Safra, and A. Wigderson · 1995
Earlier work this paper cites.
The space complexity of approximating the frequency moments
N. Alon, Y. Matias, and M. Szegedy · 1996
Earlier work this paper cites.
An elementary introduction to modern convex geometry
K. Ball · 1997
Earlier work this paper cites.
Communication Complexity
E. Kushilevitz and N. Nisan · 1997
Earlier work this paper cites.
Quantum vs. classical communication and computation
H. Buhrman, R. Cleve, and A. Wigderson · 1998
Earlier work this paper cites.
The quantum query complexity of approximating the median and related statistics
A. Nayak and F. Wu · 1999
Earlier work this paper cites.
Exponential separation of quantum and classical communication complexity
R. Raz · 1999
Earlier work this paper cites.
An isoperimetric result for the Gaussian measure and unconditional sets
F. Barthe · 2001
Earlier work this paper cites.
Quantum communication complexity of symmetric predicates
A. A. Razborov · 2002
Cited alongside, same era.
On concentration of distributions of random weighted sums
S. G. Bobkov · 2003
Cited alongside, same era.
Tight lower bounds for the distinct elements problem
P. Indyk and D. P. Woodruff · 2003
Cited alongside, same era.
Rectangle size bounds and threshold covers in communication complexity
H. Klauck · 2003
Cited alongside, same era.
Optimal space lower bounds for all frequency moments
D. P. Woodruff · 2004
Cited alongside, same era.
A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
P. Beame, T. Pitassi, N. Segerlind, and A. Wigderson · 2006
Cited alongside, same era.
The average case complexity of counting distinct elements
D. P. Woodruff · 2009
Later among the works it cites.
Better Gap-Hamming lower bounds via better round elimination
J. Brody, A. Chakrabarti, O. Regev, T. Vidick, and R. de Wolf · 2010
Closest in time.
A near-optimal algorithm for estimating the entropy of a stream
A. Chakrabarti, G. Cormode, and A. McGregor · 2010
Closest in time.
The partition bound for classical communication complexity and query complexity
R. Jain and H. Klauck · 2010
Closest in time.
A strong direct product theorem for disjointness
H. Klauck · 2010
Closest in time.
On the exact space complexity of sketching and streaming small norms
D. M. Kane, J. Nelson, and D. P. Woodruff · 2010
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
A central limit theorem for convex sets
B. Klartag · 2007
Cited alongside, same era.
Lower bounds in communication complexity based on factorization norms
N. Linial and A. Shraibman · 2007
Cited alongside, same era.
Efficient and Private Distance Approximation in the Communication and Streaming Models
D. P. Woodruff · 2007
Cited alongside, same era.
The one-way communication complexity of Gap Hamming Distance
T. S. Jayram, R. Kumar, and D. Sivakumar · 2008
Cited alongside, same era.
(Data) STRUCTURES
M. Pǎtraşcu · 2008
Cited alongside, same era.
The pattern matrix method
A. A. Sherstov · 2008
Cited alongside, same era.
The limits of two-party differential privacy
A. McGregor, I. Mironov, T. Pitassi, O. Reingold, K. Talwar, and S. P. Vadhan · 2010
Closest in time.
Property testing lower bounds via communication complexity
E. Blais, J. Brody, and K. Matulef · 2011
Closest in time.
An optimal lower bound on the communication complexity of Gap-Hamming-Distance
A. Chakrabarti and O. Regev · 2011
Closest in time.
The complexity of data aggregation in directed networks
F. Kuhn and R. Oshman · 2011
Closest in time.
A concentration inequality for the overlap of a vector on a large set, with application to the communication complexity of the Gap-Hamming-Distance problem
T. Vidick · 2011
Closest in time.
The communication complexity of gap Hamming distance
A. A. Sherstov · 2012
Closest in time.
Tight bounds for distributed functional monitoring
D. P. Woodruff and Q. Zhang · 2012
Closest in time.