Multiparty Communication Complexity and Threshold Circuit Size of AC^0
From MaRDI portal
Publication:5171163
DOI10.1109/FOCS.2009.12zbMath1292.68071OpenAlexW2103782881MaRDI QIDQ5171163
Dang-Trinh Huynh-Ngoc, P. W. Beame
Publication date: 25 July 2014
Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1109/focs.2009.12
Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (6)
Hellinger volume and number-on-the-forehead communication complexity ⋮ Hadamard tensors and lower bounds on multiparty communication complexity ⋮ Unnamed Item ⋮ The NOF multiparty communication complexity of composed functions ⋮ One-way multiparty communication lower bound for pointer jumping with applications ⋮ Communication Lower Bounds Using Directional Derivatives
This page was built for publication: Multiparty Communication Complexity and Threshold Circuit Size of AC^0