Choosing, Agreeing, and Eliminating in Communication Complexity

No abstract is available for this paper.

• Publication year

  2010

• Venue

  Computational Complexity

• Publication date

  2010-07-06

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s00037-013-0075-7
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• How to compress interactive communication

  2010cited by this paper
• Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity

  2010cited by this paper
• The Complexity of  CaRet + Chop

  2008cited by this paper
• A direct sum theorem for corruption and the multiparty NOF communication complexity of set disjointness

  2005cited by this paper
• Some connections between bounded query classes and non-uniform complexity

  2003cited by this paper
• A Direct Sum Theorem in Communication Complexity via Message Compression

  2003cited by this paper
• An information statistics approach to data stream and communication complexity

  2002cited by this paper
• Theory of Semi-Feasible Algorithms

  2002cited by this paper
• Informational complexity and the direct sum problem for simultaneous message complexity

  2001influential reference
• Towards proving strong direct product theorems

  2001cited by this paper
• The complexity of ODDnA

  2000cited by this paper
• The complexity of oddan

  2000cited by this paper
• The communication complexity of enumeration, elimination, and selection

  2000cited by this paper
• Bounded Queries in Recursion Theory

  1998cited by this paper
• On membership comparable sets

  1998cited by this paper
• One help-bit doesn't help

  1998cited by this paper
• Direct product results and the GCD problem, in old and new communication models

  1997cited by this paper
• Communication Complexity

  1997cited by this paper
• Approximable sets

  1995cited by this paper
• Super-logarithmic depth lower bounds via the direct sum in communication complexity

  1995cited by this paper
• Amortized Communication Complexity

  1995influential reference
• A direct product theorem

  1994cited by this paper
• Polynomial time truth-table reductions to p-selective sets

  1994cited by this paper
• Products and help bits in decision trees

  1994cited by this paper
• Terse, Superterse, and Verbose Sets

  1993cited by this paper
• The Probabilistic Communication Complexity of Set Intersection

  1992cited by this paper
• Fractional covers and communication complexity

  1992influential reference
• A proof of Beigel's cardinality conjecture

  1992cited by this paper
• Private vs. Common Random Bits in Communication Complexity

  1991influential reference
• Communication complexity towards lower bounds on circuit depth

  1991cited by this paper
• Super-logarithmic depth lower bounds via direct sum in communication complexity

  1991cited by this paper
• Monotone circuits for connectivity require super-logarithmic depth

  1990cited by this paper
• On the Distributional Complexity of Disjointness

  1990cited by this paper
• Enumerative counting is hard

  1988cited by this paper
• On Self-Reducibility and Weak P-Selectivity

  1983cited by this paper
• Analogues of Semicursive Sets and Effective Reducibilities to the Study of NP Complexity

  1982cited by this paper
• Reductions on NP and P-Selective Sets

  1982cited by this paper
• M. J. Fischer: On the Complexity of 2-Output Boolean Networks

  1981cited by this paper
• Some complexity questions related to distributive computing(Preliminary Report)

  1979cited by this paper
• P-Selective Sets, Tally Languages, and the Behavior of Polynomial Time Reducibilities on NP

  1979cited by this paper
• On the synthesis of self-correcting schemes from functional elements with a small number of reliable elements

  1974cited by this paper
• Realizing Boolean Functions on Disjoint sets of Variables

  1974cited by this paper
• Semirecursive sets and positive reducibility

  1968cited by this paper

• The communication complexity of functions with large outputs

  2023cites this paper
• Direct Sum Theorems From Fortification

  2022cites this paper
• The Power of Many Samples in Query Complexity

  2020cites this paper
• The choice and agreement problems of a random function

  2018cites this paper
• Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity

  2016influential citation
• Lower Bounds for Elimination via Weak Regularity

  2016cites this paper
• Direct Sum Related Problems in Communication Complexity

  2014influential citation
• On the Power of Multiplexing in Number-on-the-Forehead Protocols

  2014cites this paper
• The complexity of joint computation

  2012cites this paper
• On the Advice Complexity of Tournaments

  2012cites this paper