Non-deterministic communication complexity with few witnesses

DOI10.1016/S0022-0000(05)80049-2zbMath0821.68067OpenAlexW2176316436MaRDI QIDQ1337464

Ilan Newman, Avi Wigderson, Mauricio Karchmer, Michael E. Saks

Publication date: 6 November 1994

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(05)80049-2

zbMATH Keywords

communication complexitycommunication protocolsTuring-complexity class

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (7)

On relations between counting communication complexity classes ⋮ The landscape of communication complexity classes ⋮ Zero-information protocols and unambiguity in Arthur-Merlin communication ⋮ Deterministic Communication vs. Partition Number ⋮ On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata ⋮ Unnamed Item ⋮ Communication complexity method for measuring nondeterminism in finite automata

Cites Work

• Relations between communication complexity classes
• A new proof of a theorem of Graham and Pollak
• NP is as easy as detecting unique solutions
• Multicolored forests in bipartite decompositions of graphs
• Expressing combinatorial optimization problems by linear programs
• The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear
• Relative complexity of checking and evaluating
• Communication complexity and combinatorial lattice theory
• On the power of parity polynomial time
• On the Addressing Problem for Loop Switching
• Counting classes: Thresholds, parity, mods, and fewness
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Non-deterministic communication complexity with few witnesses