Fetching the paper…
Reading the bibliography…
A major open problem in communication complexity is whether or not quantum protocols can be exponentially more efficient than classical protocols on _total_ Boolean functions in the two-party interactive model.
Hahn polynomials, discrete harmonics and t-designs
P. Delsarte · 1978
Earlier work this paper cites.
Some complexity questions related to distributive computing
A. C.-C. Yao · 1979
Earlier work this paper cites.
Combinatorial matrices
D. Knuth · 1991
Earlier work this paper cites.
On the degree of Boolean functions as real polynomials
N. Nisan and M. Szegedy · 1992
Earlier work this paper cites.
On the degree of polynomials that approximate symmetric Boolean functions (preliminary version)
R. Paturi · 1992
Earlier work this paper cites.
Quantum circuit complexity
A. C.-C. Yao · 1993
Earlier work this paper cites.
Quantum Communication
I. Kremer · 1995
Earlier work this paper cites.
On randomized one-round communication complexity
I. Kremer, N. Nisan, and D. Ron · 1995
Earlier work this paper cites.
Communication Complexity
E. Kushilevitz and N. Nisan · 1997
Earlier work this paper cites.
On the power of quantum computation
D. R. Simon · 1997
Earlier work this paper cites.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
P. W. Shor · 1997
Earlier work this paper cites.
Quantum communication complexity of sampling
A. Ambainis, L. Schulman, A. Ta-Shma, U. Vazirani, and A. Wigderson · 1998
Earlier work this paper cites.
Quantum lower bounds by polynomials
R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf · 1998
Cited alongside, same era.
Quantum vs. classical communication and computation
H. Buhrman, R. Cleve, and A. Wigderson · 1998
Cited alongside, same era.
Quantum Entanglement and the Communication Complexity of the Inner Product Function
R. Cleve, W. van Dam, M. Nielsen, and A. Tapp · 1999
Cited alongside, same era.
Exponential separation of quantum and classical communication complexity
R. Raz · 1999
Cited alongside, same era.
Communication complexity lower bounds by polynomials
H. Buhrman and R. de Wolf · 2000
Cited alongside, same era.
Quantum lower bounds by polynomials
R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf · 2001
Cited alongside, same era.
Quantum search of spatial regions (extended abstract)
Aaronson and Ambainis · 2003
Later among the works it cites.
Rectangle size bounds and threshold covers in communication complexity
H. Klauck · 2003
Later among the works it cites.
Exponential separation of quantum and classical one-way communication complexity
Z. Bar-Yossef, T. S. Jayram, and I. Kerenidis · 2004
Later among the works it cites.
The query complexity of order-finding
R. Cleve · 2004
Later among the works it cites.
Personal communication, 2004
M. Szegedy · 2004
Later among the works it cites.
Bounded-error quantum state identification and exponential separations in communication complexity
D. Gavinsky, J. Kempe, O. Regev, and R. de Wolf · 2006
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Quantum fingerprinting
H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf · 2001
Cited alongside, same era.
Lower bounds for quantum communication complexity
H. Klauck · 2001
Cited alongside, same era.
Complexity measures and decision tree complexity: a survey
H. Buhrman and R. de Wolf · 2002
Cited alongside, same era.
Improved quantum communication complexity bounds for disjointness and equality
P. Høyer and R. de Wolf · 2002
Cited alongside, same era.
Personal communication, 2002
A. A. Razborov · 2002
Cited alongside, same era.
Quantum communication complexity of symmetric predicates (Russian)
A. A. Razborov · 2002
Cited alongside, same era.
The communication complexity of the Hamming Distance Problem
W. Huang, Y. Shi, S. Zhang, and Y. Zhu · 2006
Later among the works it cites.
Lower bounds in communication complexity based on factorization norms
N. Linial and A. Shraibman · 2007
Closest in time.
Separating AC 0 from depth-2 majority circuits
A. A. Sherstov · 2007
Closest in time.
The pattern matrix method for lower bounds on quantum communication
A. A. Sherstov · 2007
Closest in time.
Disjointness is hard in the multi-party number-on-the-forehead model
T. Lee, A. Shraibman, and R. Špalek · 2008
Closest in time.
Learning complexity vs. communication complexity
N. Linial and A. Shraibman · 2008
Closest in time.