Quantum versus Randomized Communication Complexity, with Efficient Players

Peter W. Shor: Polynominal time algorithms for discrete logarithms and factoring on a quantum computer. ANTS 1994: 289

1994

Earlier work this paper cites.

Daniel R. Simon: On the Power of Quantum Computation. FOCS 1994: 116-123

1994

Earlier work this paper cites.

Ran Raz: Fourier Analysis for Probabilistic Communication Complexity. Computational Complexity 5(3/4): 205-221 (1995)

1995

Earlier work this paper cites.

Harry Buhrman, Richard Cleve, Avi Wigderson: Quantum vs. Classical Communication and Computation. STOC 1998: 63-68

1998

Earlier work this paper cites.

Ran Raz: Exponential Separation of Quantum and Classical Communication Complexity. STOC 1999: 358-367

1999

Earlier work this paper cites.

Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis: Exponential Separation of Quantum and Classical One-Way Communication Complexity. SIAM J. Comput. 38(1): 366-384 (2008)

2008

Earlier work this paper cites.

Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de Wolf: Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography. SIAM J. Comput. 38(5): 1695-1708 (2008)

2008

Cited alongside, same era.

Scott Aaronson: BQP and the polynomial hierarchy. STOC 2010: 141-150

2010

Cited alongside, same era.

Oded Regev, Boàz Klartag: Quantum one-way communication can be exponentially stronger than classical communication. STOC 2011: 31-40

2011

Cited alongside, same era.

Ryan O’Donnell: Analysis of Boolean Functions. Cambridge University Press 2014, ISBN 978-1-10-703832-5, pp. I-XX, 1-423

2014

Cited alongside, same era.

Scott Aaronson and Andris Ambainis: Forrelation: A Problem That Optimally Separates Quantum from Classical Computing. STOC 2015. 307-316

2015

Cited alongside, same era.

Mika Göös, Toniann Pitassi, Thomas Watson: Query-to-Communication Lifting for BPP. FOCS 2017: 132-143

2017

Later among the works it cites.

Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett: Pseudorandom Generators from Polarizing Random Walks. CCC 2018: 1:1-1:21

2018

Later among the works it cites.

Hamed Hatami, Kaave Hosseini, Shachar Lovett: Structure of Protocols for XOR Functions. SIAM J. Comput. 47(1): 208-217 (2018)

2018

Later among the works it cites.

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi: Query-To-Communication Lifting for BPP Using Inner Product. ICALP 2019: 35:1-35:15

2019

Closest in time.

Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal: Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates. ITCS 2019: 22:1-22:15

2019