Computer Science – Computational Complexity
Scientific paper
2009-02-18
Computer Science
Computational Complexity
Scientific paper
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 \in 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_{\max} \cdot \log |G|)$ communication, where $d_{\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_{\max} \cdot \log p)$ communication, where $d_{\max}$ is the maximum of the dimensions of the irreducible $\F_p$-representations of $G$.
Aaronson Scott
Gall François Le
Russell Alexander
Tani Seiichiro
No associations
LandOfFree
The One-Way Communication Complexity of Group Membership does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The One-Way Communication Complexity of Group Membership, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The One-Way Communication Complexity of Group Membership will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-128689