Nondeterministic and randomized Boolean hierarchies in communication complexity
From MaRDI portal
Publication:2041245
DOI10.1007/s00037-021-00210-5OpenAlexW3182730461MaRDI QIDQ2041245
Publication date: 16 July 2021
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-021-00210-5
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Zero-information protocols and unambiguity in Arthur-Merlin communication
- An information statistics approach to data stream and communication complexity
- Boolean function complexity. Advances and frontiers.
- Relations between communication complexity classes
- Bounded queries to SAT and the Boolean hierarchy
- On the distributional complexity of disjointness
- The landscape of communication complexity classes
- Separation of the monotone NC hierarchy
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- Different Modes of Communication
- The difference and truth-table hierarchies for NP
- The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
- CREW PRAM<scp>s</scp> and Decision Trees
- The Probabilistic Communication Complexity of Set Intersection
- Deterministic Communication vs. Partition Number
- A decisive characterization of BPP
- Communication Complexity
- Probabilistic rank and matrix rigidity
- Equality alone does not simulate randomness
- Query-to-Communication Lifting for BPP
- A ZPP NP[1 Lifting Theorem]
- Rectangles Are Nonnegative Juntas
