The randomized communication complexity of set disjointness

DOI10.4086/TOC.2007.V003A011MaRDI QIDQ3002788zbMATH OpenOpenAlexFDO

Authors A. Wigderson, Johan Hastad

Publication date 24 May 2011

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NoDerivs 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2007.v003a011

zbMATH Keywords

communication complexityrandomized protocolset disjointness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The multiparty communication complexity of set disjointness
• Sparse and Lopsided Set Disjointness via Information Theory
• Simplified lower bounds on the multiparty communication complexity of disjointness
• The multiparty communication complexity of set disjointness
• Communication complexity of set-disjointness for all probabilities

Cited in

(29)

• A communication-randomness tradeoff for two-processor systems
• Property testing lower bounds via a generalization of randomized parity decision trees
• Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond
• Fooling views: a new lower bound technique for distributed computations under congestion
• Communication complexity of set-disjointness for all probabilities
• Fooling pairs in randomized communication complexity
• Communication complexity theory: thirty-five years of set disjointness
• scientific article; zbMATH DE number 6696541 (Why is no real title available?)
• Lower Bounds for Testing Computability by Small Width OBDDs
• Sparse and Lopsided Set Disjointness via Information Theory
• Certifying equality with limited interaction
• The Simultaneous Communication of Disjointness with Applications to Data Streams
• The Probabilistic Communication Complexity of Set Intersection
• scientific article; zbMATH DE number 177818 (Why is no real title available?)
• The communication complexity of the inevitable intersection problem
• A lower bound for sampling disjoint sets
• Equality alone does not simulate randomness
• Distributed Testing of Distance-k Colorings
• Best-order streaming model
• The communication complexity of set intersection and multiple equality testing
• scientific article; zbMATH DE number 7650118 (Why is no real title available?)
• LATIN 2004: Theoretical Informatics
• Superfast coloring in CONGEST via efficient color sampling
• Superfast coloring in CONGEST via efficient color sampling
• Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
• Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
• Communication and information complexity
• Streaming and query once space complexity of longest increasing subsequence
• Property testing lower bounds via communication complexity

This page was built for publication: The randomized communication complexity of set disjointness

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