A new exponential separation between quantum and classical one-way communication complexity

Étude des coefficients Fourier des fonctiones de Lp(G)

A. Bonami · 1970

Earlier work this paper cites.

Inequalities in Fourier analysis

W. Beckner · 1975

Earlier work this paper cites.

Some complexity questions related to distributive computing

A. Yao · 1979

Earlier work this paper cites.

The Theory of Error-Correcting Codes

F. J. MacWilliams and N. J. A. Sloane · 1983

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.

Fourier analysis for probabilistic communication complexity

R. Raz · 1995

Earlier work this paper cites.

Estimates for the range of binomiality in codes’ spectra

I. Krasikov and S. Litsyn · 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.

Survey of binary Krawtchouk polynomials

I. Krasikov and S. Litsyn · 1999

Cited alongside, same era.

Exponential separation of quantum and classical communication complexity

R. Raz · 1999

Cited alongside, same era.

Succinct quantum proofs for properties of finite groups

J. Watrous · 2000

Cited alongside, same era.

Quantum fingerprinting

H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf · 2001

Cited alongside, same era.

Linear codes and character sums

N. Linial and A. Samorodnitsky · 2002

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.

Bounds on distance distributions in codes of known size

A. Ashikhmin, G. Cohen, M. Krivelevich, and S. Litsyn · 2005

Later among the works it cites.

Data streams: algorithms and applications

S. Muthukrishnan · 2005

Later among the works it cites.

Exponential separation of quantum and classical one-way communication complexity for a boolean function, 2006

D. Gavinsky, J. Kempe, and R. de Wolf · 2006

Later among the works it cites.

The one-way communication complexity of the Boolean Hidden Matching Problem, 2006

I. Kerenidis and R. Raz · 2006

Later among the works it cites.

Exponential separations for one-way quantum communication complexity, with applications to cryptography

D. Gavinsky, J. Kempe, I. Kerenidis, R. Raz, and R. de Wolf · 2008

Later among the works it cites.

A brief introduction to Fourier analysis on the boolean cube