Disjointness is hard in the multiparty number-on-the-forehead model

DOI10.1007/s00037-009-0276-2zbMath1213.68314OpenAlexW2172507717MaRDI QIDQ626627

Troy Lee, Adi Shraibman

Publication date: 18 February 2011

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-009-0276-2

zbMATH Keywords

communication complexityproof complexitydisjointnessnumber-on-the-forehad model

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Hellinger volume and number-on-the-forehead communication complexity ⋮ Interactive Information Complexity ⋮ Breaking the Minsky--Papert Barrier for Constant-Depth Circuits ⋮ Interactive Information Complexity ⋮ Hadamard tensors and lower bounds on multiparty communication complexity ⋮ Towards NP-P via proof complexity and search ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Communication and information complexity ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ Algorithmic Polynomials ⋮ The NOF multiparty communication complexity of composed functions ⋮ The hardest halfspace ⋮ One-way multiparty communication lower bound for pointer jumping with applications ⋮ Kolmogorov complexity and combinatorial methods in communication complexity ⋮ Rectangles Are Nonnegative Juntas ⋮ The Multiparty Communication Complexity of Set Disjointness ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Communication Lower Bounds Using Directional Derivatives