Choosing, agreeing, and eliminating in communication complexity

DOI10.1007/S00037-013-0075-7zbMATH Open1366.68050OpenAlexW2039983178MaRDI QIDQ744609FDOQ744609

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

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

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)

Cites Work

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

Cited In (5)

• 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

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)