Fetching the paper…
Reading the bibliography…
In STOC 1999, Raz presented a (partial) function for which there is a quantum protocol communicating only $O(\log n)$ qubits, but for which any classical (randomized, bounded-error) protocol requires $\poly(n)$ bits of communication.
Spherical harmonics , volume 17 of Lecture Notes in Mathematics
C. Müller · 1966
Earlier work this paper cites.
A quartic interaction in two dimensions
E. Nelson · 1966
Earlier work this paper cites.
Étude des coefficients de Fourier des fonctions de L p ( G ) L^{p}(G)
A. Bonami · 1970
Earlier work this paper cites.
Introduction to Fourier analysis on Euclidean spaces
E. M. Stein and G. Weiss · 1971
Earlier work this paper cites.
Inequalities in Fourier analysis
W. Beckner · 1975
Earlier work this paper cites.
Logarithmic Sobolev inequalities
L. Gross · 1975
Earlier work this paper cites.
Diffusions hypercontractives
D. Bakry and M. Émery · 1985
Earlier work this paper cites.
Asymptotic theory of finite-dimensional normed spaces , volume 1200 of Lecture Notes in Mathematics
V. D. Milman and G. Schechtman · 1986
Earlier work this paper cites.
Hypercontractivity and the Bakry-Emery criterion for compact Lie groups
O. S. Rothaus · 1986
Earlier work this paper cites.
The influence of variables on Boolean functions
J. Kahn, G. Kalai, and N. Linial · 1988
Earlier work this paper cites.
Quantum circuit complexity
A. C.-C. Yao · 1993
Cited alongside, same era.
Quantum Communication
I. Kremer · 1995
Cited alongside, same era.
Communication Complexity
E. Kushilevitz and N. Nisan · 1997
Cited alongside, same era.
The quantum communication complexity of sampling
A. Ambainis, L. J. Schulman, A. Ta-Shma, U. Vazirani, and A. Wigderson · 1998
Cited alongside, same era.
Quantum vs. classical communication and computation
H. Buhrman, R. Cleve, and A. Wigderson · 1998
Cited alongside, same era.
The Radon transform , volume 5 of Progress in Mathematics
S. Helgason · 1999
Cited alongside, same era.
Exponential separation of quantum and classical communication complexity
Classical interaction cannot replace a quantum message
D. Gavinsky · 2008
Later among the works it cites.
Exponential separation for one-way quantum communication complexity, with applications to cryptography
D. Gavinsky, J. Kempe, I. Kerenidis, R. Raz, and R. d. Wolf · 2008
Later among the works it cites.
Simultaneous communication protocols with quantum and classical messages
D. Gavinsky, O. Regev, and R. d. Wolf · 2008
Later among the works it cites.
A Brief Introduction to Fourier Analysis on the Boolean Cube
R. d. Wolf · 2008
Later among the works it cites.
Classical interaction cannot replace quantum nonlocality, 2009
D. Gavinsky · 2009
Later among the works it cites.
An optimal lower bound on the communication complexity of gap Hamming distance, 2010
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
R. Raz · 1999
Cited alongside, same era.
Some remarks on a lemma of Ran Raz
V. Milman and R. Wagner · 2003
Cited alongside, same era.
Exponential separation of quantum and classical one-way communication complexity
Z. Bar-Yossef, T. S. Jayram, and I. Kerenidis · 2004
Cited alongside, same era.
A logarithmic Sobolev form of the Li-Yau parabolic inequality
D. Bakry and M. Ledoux · 2006
Cited alongside, same era.
A. Chakrabarti and O. Regev · 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.
A new exponential separation between quantum and classical one-way communication complexity, 2010
A. Montanaro · 2010
Closest in time.