Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits

DOI10.1145/2897518.2897636zbMath1373.68220arXiv1511.07860OpenAlexW2175125908MaRDI QIDQ5361867

Daniel M. Kane, R. Ryan Williams

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.07860

zbMATH Keywords

circuit complexityrandom restrictionsaverage-case complexitythreshold circuitsLittlewood-Offord problems

Mathematics Subject Classification ID

Related Items (16)

Local reduction ⋮ A Short List of Equalities Induces Large Sign-Rank ⋮ A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics ⋮ Unnamed Item ⋮ String Matching: Communication, Circuits, and Learning. ⋮ Size, Depth and Energy of Threshold Circuits Computing Parity Function. ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Hardness magnification near state-of-the-art lower bounds ⋮ Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ Computing majority by constant depth majority circuits with low fan-in gates ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle ⋮ Upper bound for torus polynomials ⋮ A \#SAT algorithm for small constant-depth circuits with PTF gates

This page was built for publication: Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits