Choosing, agreeing, and eliminating in communication complexity

DOI10.1007/s00037-013-0075-7zbMath1366.68050OpenAlexW2039983178MaRDI QIDQ744609

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

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)

Related Items (3)

Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity ⋮ The communication complexity of functions with large outputs ⋮ The choice and agreement problems of a random function

Cites Work

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

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