Nondeterministic and randomized Boolean hierarchies in communication complexity
type: Item
instance of: scholarly article
title: Nondeterministic and randomized Boolean hierarchies in communication complexity
author: Yanyan Li
published in: Computational Complexity
publication date: 2021-07-16T00:00:00Z
Mathematics Subject Classification ID: 68Q11
zbMATH DE Number: 7372274
zbMATH Keywords: Boolean hierarchies
zbMATH Keywords: lifting theorems
zbMATH Keywords: query complexity
MaRDI profile type: Publication
full work available at URL: s00037-021-00210-5
OpenAlex ID: W3182730461
cites work: Probabilistic rank and matrix rigidity
cites work: An information statistics approach to data stream and communication complexity
cites work: Bounded queries to SAT and the Boolean hierarchy
cites work: Q3974853
cites work: Q3751004
cites work: Equality alone does not simulate randomness
cites work: Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
cites work: Rectangles are nonnegative juntas
cites work: Zero-information protocols and unambiguity in Arthur-Merlin communication
cites work: Deterministic Communication vs. Partition Number
cites work: The landscape of communication complexity classes
cites work: Query-to-Communication Lifting for BPP
cites work: Relations between communication complexity classes
cites work: Different Modes of Communication
cites work: Boolean function complexity. Advances and frontiers.
cites work: The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
cites work: The Probabilistic Communication Complexity of Set Intersection
cites work: The difference and truth-table hierarchies for NP
cites work: Communication Complexity
cites work: Q5090432
cites work: CREW PRAM<scp>s</scp> and Decision Trees
cites work: Separation of the monotone NC hierarchy
cites work: On the distributional complexity of disjointness
cites work: A ZPP NP[1] Lifting Theorem
cites work: Q3703297
cites work: A decisive characterization of BPP
DOI: 10.1007/S00037-021-00210-5
description: scientific article; zbMATH DE number 7372274