The One-Way Communication Complexity of Group Membership

Probabilistic methods in group theory

P. Erdős and A. Rényi · 1965

Earlier work this paper cites.

On the uniform convergence of relative frequencies of events to their probabilities

Vladimir Vapnik and Alexey Chervonenkis · 1971

Earlier work this paper cites.

Character theory of finite groups

I. Martin Isaacs · 1976

Earlier work this paper cites.

Linear representations of finite groups

Jean-Pierre Serre · 1977

Earlier work this paper cites.

The largest irreducible degree of a finite group

David Gluck · 1985

Earlier work this paper cites.

Local expansion of vertex-transitive graphs and random generation in finite groups

László Babai · 1991

Earlier work this paper cites.

The probabilistic communication complexity of set intersection

Bala Kalyanasundaram and Georg Schnitger · 1992

Earlier work this paper cites.

Maximal subgroups in finite and profinite groups

Alexander Borovik, Laszlo Pyber, and Aner Shalev · 1996

Earlier work this paper cites.

Public vs. private coin flips in one round communication games (extended abstract)

Ilan Newman and Mario Szegedy · 1996

Cited alongside, same era.

On data structures and asymmetric communication complexity

Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson · 1998

Cited alongside, same era.

Succinct quantum proofs for properties of finite groups

John Watrous · 2000

Cited alongside, same era.

Quantum fingerprinting

Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf · 2001

Cited alongside, same era.

Lectures on discrete geometry

Jiri Matousek · 2002

Cited alongside, same era.

The hidden subgroup problem and quantum computation using group representations

Sean Hallgren, Alexander Russell, and Amnon Ta-Shma · 2003

Cited alongside, same era.

Quantum search of spatial regions

Scott Aaronson and Andris Ambainis · 2005

Later among the works it cites.

Limitations of quantum advice and one-way communication

Scott Aaronson · 2005

Later among the works it cites.

Representation theory of finite groups and associative algebras

Charles W. Curtis and Irving Reiner · 2006

Later among the works it cites.

Expander graphs and their applications

S. Hoory, N. Linial, and A. Wigderson · 2006

Later among the works it cites.

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

Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf · 2007

Later among the works it cites.

Unbounded-error one-way classical and quantum communication complexity

Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, and Shigeru Yamashita · 2007

Later among the works it cites.