Published by the Department of Computer Science, The University of Chicago.
The One-Way Communication Complexity of Subgroup Membership
Massachussetts Institute of Technology
François Le Gall
The University of Tokyo
University of Connecticut
December 20, 2011
This paper studies the one-way communication complexity of the subgroup membership problem,
a classical problem closely related to basic questions in quantum computing. Here Alice receives,
as input, a subgroup H of a finite group G; Bob receives an element y of G. Alice is permitted
to send a single message to Bob, after which he must decide if his input y is an element of H.
We establish the following bounds on the classical communication complexity of this problem in
the bounded-error setting:
- The problem can be solved with O( log |G|)-bit communication with the promise that H is normal.
- The problem can be solved with O(dmax log |G|)-bit communication, where dmax
is the maximum degree of an irreducible complex representation of G.
- For any prime p not dividing |G|, the problem can be solved with
O(log |G| + dmax log p)-bit communication, where dmax is the maximum degree of
an irreducible Fp-representation of G.
- The article: PDF (263K bytes)
- Source material: ZIP (77K bytes)
- BibTeX entry for this article (315 bytes)
Submitted June 9, 2010, resubmitted December 5, 2011, published December 20, 2011.
Article recompiled to the new format on May 7, 2012. No change was
made to the test but the publication date was misstated. The
article was recompiled again on July 8, 2014; again, no change
was made to the text but the publication date was corrected.
Click here for the the original December 2011 version and
here for the May 2012 version.
Volume 2011, Article 5
Volume 2012, Article 1