Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR19-043 | 8th July 2021 20:04

Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity

RSS-Feed




Revision #1
Authors: Toniann Pitassi, Morgan Shirley, Thomas Watson
Accepted on: 8th July 2021 20:04
Downloads: 358
Keywords: 


Abstract:

We investigate the power of randomness in two-party communication complexity. In particular, we study the model where the parties can make a constant number of queries to a function that has an efficient one-sided-error randomized protocol. The complexity classes defined by this model comprise the Randomized Boolean Hierarchy, which is analogous to the Boolean Hierarchy but defined with one-sided-error randomness instead of nondeterminism. Our techniques connect the Nondeterministic and Randomized Boolean Hierarchies, and we provide a complete picture of the relationships among complexity classes within and across these two hierarchies. In particular, we prove that the Randomized Boolean Hierarchy does not collapse, and we prove a query-to-communication lifting theorem for all levels of the Nondeterministic Boolean Hierarchy and use it to resolve an open problem stated in the paper by Halstenberg and Reischuk (CCC 1988) which initiated the study of this hierarchy.


Paper:

TR19-043 | 12th March 2019 20:55

Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity





TR19-043
Authors: Toniann Pitassi, Morgan Shirley, Thomas Watson
Publication: 24th March 2019 09:12
Downloads: 960
Keywords: 


Abstract:

We study the Boolean Hierarchy in the context of two-party communication complexity, as well as the analogous hierarchy defined with one-sided error randomness instead of nondeterminism. Our results provide a complete picture of the relationships among complexity classes within and across these two hierarchies. In particular, we prove a query-to-communication lifting theorem for all levels of the Boolean Hierarchy and use it to resolve an open problem stated in the paper by Halstenberg and Reischuk (CCC 1988) which initiated this topic.



ISSN 1433-8092 | Imprint