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 (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.

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

Volume 2011, Article 5

Volume 2011

Published articles