The multiparty communication complexity of set disjointness

DOI10.1145/2213977.2214026zbMath1286.94118OpenAlexW2044859592MaRDI QIDQ5415499

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 complexitymultiparty communication complexitydirect product theoremsset disjointness problem

Mathematics Subject Classification ID

Related Items (14)

Hellinger volume and number-on-the-forehead communication complexity ⋮ Hardness Amplification and the Approximate Degree of Constant-Depth Circuits ⋮ A Hierarchy Theorem for Interactive Proofs of Proximity ⋮ Interactive Information Complexity ⋮ Interactive Information Complexity ⋮ Communication and information complexity ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ The NOF multiparty communication complexity of composed functions ⋮ Non-interactive proofs of proximity ⋮ Simulation theorems via pseudo-random properties ⋮ Rectangles Are Nonnegative Juntas ⋮ Lifting Theorems for Equality ⋮ Communication Lower Bounds Using Directional Derivatives ⋮ Dual lower bounds for approximate degree and Markov-Bernstein inequalities

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