The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection

No abstract is available for this paper.

• Publication year

  2009

• Venue

  2009 50th Annual IEEE Symposium on Foundations of Computer Science

• Publication date

  2009-10-25

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/FOCS.2009.15
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Communication Complexity

  2016cited by this paper
• On the complexity of communication complexity

  2009cited by this paper
• The Randomized Communication Complexity of Set Disjointness

  2007influential reference
• An information statistics approach to data stream and communication complexity

  2002cited by this paper
• A characterization of span program size and improved lower bounds for monotone span programs

  1998cited by this paper
• The Linear-Array Conjecture in Communication Complexity Is False

  1996cited by this paper
• Lower bounds for monotone span programs

  1995cited by this paper
• Monotone Separation of Logarithmic Space from Logarithmic Depth

  1995cited by this paper
• Amortized Communication Complexity

  1995cited by this paper
• On rank vs. communication complexity

  1994influential reference
• The Probabilistic Communication Complexity of Set Intersection

  1992influential reference
• A Simple Lower Bound for Monotone Clique Using a Communication Game

  1992cited by this paper
• Expressing combinatorial optimization problems by linear programs

  1991cited by this paper
• Communication complexity towards lower bounds on circuit depth

  1991influential reference
• On the Distributional Complexity of Disjointness

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

  1990influential reference
• Applications of matrix methods to the theory of lower bounds in computational complexity

  1990cited by this paper
• Las Vegas is better than determinism in VLSI and distributed computing (Extended Abstract)

  1982influential reference

• Lifting Theorems Meet Information Complexity: Known and New Lower Bounds of Set-disjointness

  2023cites this paper
• The White-Box Adversarial Data Stream Model

  2022cites this paper
• A Lower Bound for Sampling Disjoint Sets

  2020cites this paper
• On the Gap Between Deterministic Communication Complexity and the Partition

  2018cites this paper
• Certifying Equality With Limited Interaction

  2016cites this paper
• Lower Bounds for Clique vs. Independent Set

  2015cites this paper
• Distributed computation in wireless and dynamic networks

  2012cites this paper
• Cs 2429 -foundations of Communication Complexity Cs 2429 -foundations of Communication Complexity

  2012influential citation
• Network-aware mechanisms for tolerating Byzantine failures in distributed systems

  2012cites this paper
• Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds

  2011cites this paper
• Exponential Lower Bounds for Polytopes in Combinatorial Optimization

  2011cites this paper
• Multiparty Equality Function Computation in Networks with Point-to-Point Links

  2010cites this paper