Multiparty Communication Complexity and Threshold Circuit Size of AC^0

DOI10.1109/FOCS.2009.12MaRDI QIDQ5171163zbMATH OpenOpenAlexFDO

Authors Dang-Trinh Huynh-Ngoc, Paul 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

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited in

(6)

• Hellinger volume and number-on-the-forehead communication complexity
• Hadamard tensors and lower bounds on multiparty communication complexity
• 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
• scientific article; zbMATH DE number 7650118 (Why is no real title available?)

This page was built for publication: Multiparty Communication Complexity and Threshold Circuit Size of AC^0

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