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 (263,502 bytes)
- Source material: ZIP (59,599 bytes)
- BibTeX entry for this article (315 bytes)
Submitted June 9, 2010, resubmitted December 5, 2011, published December 20, 2011.
Article recompiled in new format on May 7, 2012; no change was made to the text. Click here for the original version.
Volume 2011, Article 5