Published by the Department of Computer Science, The University of Chicago.

Abstract

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:

1. The problem can be solved with O( log |G|)-bit communication with the promise that H is normal.
2. 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.
3. 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.

© 2011 Scott Aaronson, François Le Gall, Alexander Russell, and Seiichiro Tani
Licensed under a Creative Commons Attribution License

Volume 2011, Article 5

Volume 2012, Article 1

Volume 2011

Published articles