The multiparty communication complexity of set disjointness

DOI10.1145/2213977.2214026MaRDI QIDQ5415499zbMATH OpenOpenAlexFDO

Authors Alexander A. Sherstov

Publication date 13 May 2014

Published in Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2213977.2214026

zbMATH Keywords

circuit complexitydirect product theoremsmultiparty communication complexityset disjointness problem

Mathematics Subject Classification ID

Recommendations

• The multiparty communication complexity of set disjointness
• Simplified lower bounds on the multiparty communication complexity of disjointness
• A strong direct product theorem for disjointness
• Inner product and set disjointness: beyond logarithmically many parties
• Disjointness is hard in the multiparty number-on-the-forehead model

Cited in

(33)

• Non-interactive proofs of proximity
• A note on multiparty communication complexity and the Hales-Jewett theorem
• On multi-partition communication complexity
• Simulation theorems via pseudo-random properties
• A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
• New strong direct product results in communication complexity
• Communication complexity of set-disjointness for all probabilities
• The multiparty communication complexity of set disjointness
• Communication complexity theory: thirty-five years of set disjointness
• Hellinger volume and number-on-the-forehead communication complexity
• scientific article; zbMATH DE number 6696541 (Why is no real title available?)
• The randomized communication complexity of set disjointness
• Hardness amplification and the approximate degree of constant-depth circuits
• The Simultaneous Communication of Disjointness with Applications to Data Streams
• Interactive Information Complexity
• Partition Arguments in Multiparty Communication Complexity
• Hadamard tensors and lower bounds on multiparty communication complexity
• The Probabilistic Communication Complexity of Set Intersection
• Interactive information complexity
• Simplified lower bounds on the multiparty communication complexity of disjointness
• A hierarchy theorem for interactive proofs of proximity
• scientific article; zbMATH DE number 1419257 (Why is no real title available?)
• The NOF multiparty communication complexity of composed functions
• Lifting Theorems for Equality
• A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
• scientific article; zbMATH DE number 6292585 (Why is no real title available?)
• Communication lower bounds using directional derivatives
• Automata, Languages and Programming
• Inner product and set disjointness: beyond logarithmically many parties
• Rectangles are nonnegative juntas
• Improved separations between nondeterministic and randomized multiparty communication
• Communication and information complexity
• Disjointness is hard in the multiparty number-on-the-forehead model

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

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