Choosing, agreeing, and eliminating in communication complexity

DOI10.1007/S00037-013-0075-7MaRDI QIDQ744609zbMATH OpenOpenAlexFDO

Authors Amos Beimel, Sebastian Ben Daniel, Eyal Kushilevitz, Enav Weinreb

Publication date 25 September 2014

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.190.8101

zbMATH Keywords

selectioncommunication complexityeliminationdirect sum

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• Choosing, agreeing, and eliminating in communication complexity
• The communication complexity of enumeration, elimination, and selection
• A three-party communication problem
• Lower bounds for elimination via weak regularity
• The choice and agreement problems of a random function

Cites work

• scientific article; zbMATH DE number 177818 (Why is no real title available?)
• scientific article; zbMATH DE number 2038719 (Why is no real title available?)
• scientific article; zbMATH DE number 1559552 (Why is no real title available?)
• scientific article; zbMATH DE number 1775396 (Why is no real title available?)
• A proof of Beigel's cardinality conjecture
• A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
• Amortized Communication Complexity
• An information statistics approach to data stream and communication complexity
• Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
• Bounded queries in recursion theory
• Communication Complexity
• Communication complexity towards lower bounds on circuit depth
• Enumerative counting is hard
• Fractional Covers and Communication Complexity
• How to compress interactive communication
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• On membership comparable sets
• On self-reducibility and weak P-selectivity
• On the complexity of 2-output Boolean networks
• On the synthesis of self-correcting schemes from functional elements with a small number of reliable elements
• Optimal direct sum results for deterministic and randomized decision tree complexity
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Private vs. common random bits in communication complexity
• Products and Help Bits in Decision Trees
• Reductions on NP and p-selective sets
• Semirecursive Sets and Positive Reducibility
• Some connections between bounded query classes and non-uniform complexity.
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• Terse, superterse, and verbose sets
• The Probabilistic Communication Complexity of Set Intersection
• The communication complexity of enumeration, elimination, and selection
• The complexity of ODD_n^A
• Theory of semi-feasible algorithms

Cited in

(6)

• The communication complexity of functions with large outputs
• Choosing, agreeing, and eliminating in communication complexity
• The communication complexity of enumeration, elimination, and selection
• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
• The choice and agreement problems of a random function
• Lower bounds for elimination via weak regularity

This page was built for publication: Choosing, agreeing, and eliminating in communication complexity

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