Multiparty Communication Complexity and Threshold Circuit Size of $\ensuremath{\sfAC}^0$
From MaRDI portal
Publication:2910850
DOI10.1137/100792779zbMath1269.68054OpenAlexW2036908068MaRDI QIDQ2910850
Trinh N. D. Huynh, P. W. Beame
Publication date: 12 September 2012
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/100792779
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
Breaking the Minsky--Papert Barrier for Constant-Depth Circuits, The Power of Asymmetry in Constant-Depth Circuits, Unnamed Item, A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$, Algorithmic Polynomials, New algorithms and lower bounds for circuits with linear threshold gates, The hardest halfspace, Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$, The Multiparty Communication Complexity of Set Disjointness, Unnamed Item, Unnamed Item
