On the complexity of communication complexity

DOI10.1145/1536414.1536479MaRDI QIDQ5172741zbMATH OpenOpenAlexFDO

Authors Eyal Kushilevitz, Enav Weinreb

Publication date 4 February 2015

Published in Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1536414.1536479

zbMATH Keywords

communication complexityhardness of approximationlower boundsprotocol treepseudo random functions

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Communication complexity
• Communication Complexity
• scientific article; zbMATH DE number 1361464
• scientific article; zbMATH DE number 3881884
• Communication complexity
• scientific article; zbMATH DE number 4147508
• scientific article; zbMATH DE number 4197419
• Communication Complexity
• scientific article; zbMATH DE number 2146643

Cited in

(19)

• On the P versus NP intersected with co-NP question in communication complexity
• Communication complexity of two decision problems
• Non-deterministic communication complexity with few witnesses
• Recognition problems and communication complexity.
• Ordered biclique partitions and communication complexity problems
• Some improved bounds on communication complexity via new decomposition of cliques
• Individual communication complexity
• Exponential lower bounds for polytopes in combinatorial optimization
• The Complexity of Complexity
• scientific article; zbMATH DE number 4147508 (Why is no real title available?)
• Average and randomized communication complexity
• On Toda’s Theorem in Structural Communication Complexity
• scientific article; zbMATH DE number 66621 (Why is no real title available?)
• Rounds in Communication Complexity Revisited
• scientific article; zbMATH DE number 7561750 (Why is no real title available?)
• Communication Complexity
• The communication complexity of addition
• On the extension complexity of polytopes separating subsets of the Boolean cube
• The cost of the missing bit: Communication complexity with help

This page was built for publication: On the complexity of communication complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5172741)