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: | Le Gall, Francois, Tani, Seiichiro, Russell, Alexander, Aaronson, Scott |
---|---|
Other Authors: | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
Format: | Article |
Language: | en_US |
Published: |
2010
|
Online Access: | http://hdl.handle.net/1721.1/54762 https://orcid.org/0000-0003-1333-4045 |
Similar Items
-
Group Membership and Parthood
by: David Strohmaier
Published: (2019-04-01) -
Group Membership and Parthood
by: Strohmaier David
Published: (2019-04-01) -
On relating one-way classical and quantum communication complexities
by: Naresh Goud Boddu, et al.
Published: (2023-05-01) -
Anonymous authentication of membership in dynamic groups
by: Parnell, Todd C., 1977-
Published: (2013) -
Anonymous authentication of membership in dynamic groups
by: Parnell, Todd C., 1977-
Published: (2013)