Exponential lower bounds for depth three Boolean circuits
From MaRDI portal
Publication:1590079
DOI10.1007/PL00001598zbMath0963.68147MaRDI QIDQ1590079
Ramamohan Paturi, Francis Zane, Michael E. Saks
Publication date: 19 December 2000
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/pl00001598
68Q99: Theory of computing
Related Items
Unnamed Item, Parity helps to compute majority, The complexity of depth-3 circuits computing symmetric Boolean functions, Gate elimination: circuit size lower bounds and \#SAT upper bounds, Subset sum ``cubes and the complexity of primality testing, Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits, The Complexity of Satisfiability of Small Depth Circuits