The one-way communication complexity of group membership
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 x ∈ G. Alice is permitted to send a singl...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
2010
|
| Online Access: | http://hdl.handle.net/1721.1/54762 https://orcid.org/0000-0003-1333-4045 |
| _version_ | 1811086788629889024 |
|---|---|
| author | Le Gall, Francois Tani, Seiichiro Russell, Alexander Aaronson, Scott |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Le Gall, Francois Tani, Seiichiro Russell, Alexander Aaronson, Scott |
| author_sort | Le Gall, Francois |
| collection | MIT |
| description | 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 x ∈ G. Alice is permitted to send a single
message to Bob, after which he must decide if his input x is an element of H. We prove the following upper bounds on the classical communication complexity of this problem in the bounded-error setting: 1. The problem can be solved with O(log|G|) communication, provided the subgroup H is normal.
2. The problem can be solved with O(d[subscript max] · log|G|) communication, where d[subscript max] is the maximum of
the dimensions of the irreducible complex representations of G.
3. For any prime p not dividing |G|, the problem can be solved with O(d[subscript max] · log p) communication,
where d[subscript max] is the maximum of the dimensions of the irreducible Fp-representations of G. |
| first_indexed | 2024-09-23T13:34:45Z |
| format | Article |
| id | mit-1721.1/54762 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:34:45Z |
| publishDate | 2010 |
| record_format | dspace |
| spelling | mit-1721.1/547622022-10-01T15:49:08Z The one-way communication complexity of group membership Le Gall, Francois Tani, Seiichiro Russell, Alexander Aaronson, Scott Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Aaronson, Scott Aaronson, Scott 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 x ∈ G. Alice is permitted to send a single message to Bob, after which he must decide if his input x is an element of H. We prove the following upper bounds on the classical communication complexity of this problem in the bounded-error setting: 1. The problem can be solved with O(log|G|) communication, provided the subgroup H is normal. 2. The problem can be solved with O(d[subscript max] · log|G|) communication, where d[subscript max] is the maximum of the dimensions of the irreducible complex representations of G. 3. For any prime p not dividing |G|, the problem can be solved with O(d[subscript max] · log p) communication, where d[subscript max] is the maximum of the dimensions of the irreducible Fp-representations of G. 2010-05-11T20:26:42Z 2010-05-11T20:26:42Z 2009-02 Article http://purl.org/eprint/type/SubmittedJournalArticle CoRR, Vol. abs/0902.3175 (2009) http://hdl.handle.net/1721.1/54762 Aaronson, Scott, Francois Le Gall, Alexander Russell and Seiichiro Tani. "The One-Way Communication Complexity of Group Membership." https://orcid.org/0000-0003-1333-4045 en_US Attribution-Noncommercial-Share Alike 3.0 Unported http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf arXiv |
| spellingShingle | Le Gall, Francois Tani, Seiichiro Russell, Alexander Aaronson, Scott The one-way communication complexity of group membership |
| title | The one-way communication complexity of group membership |
| title_full | The one-way communication complexity of group membership |
| title_fullStr | The one-way communication complexity of group membership |
| title_full_unstemmed | The one-way communication complexity of group membership |
| title_short | The one-way communication complexity of group membership |
| title_sort | one way communication complexity of group membership |
| url | http://hdl.handle.net/1721.1/54762 https://orcid.org/0000-0003-1333-4045 |
| work_keys_str_mv | AT legallfrancois theonewaycommunicationcomplexityofgroupmembership AT taniseiichiro theonewaycommunicationcomplexityofgroupmembership AT russellalexander theonewaycommunicationcomplexityofgroupmembership AT aaronsonscott theonewaycommunicationcomplexityofgroupmembership AT legallfrancois onewaycommunicationcomplexityofgroupmembership AT taniseiichiro onewaycommunicationcomplexityofgroupmembership AT russellalexander onewaycommunicationcomplexityofgroupmembership AT aaronsonscott onewaycommunicationcomplexityofgroupmembership |