Exponential lower bounds for depth three Boolean circuits

DOI10.1007/PL00001598zbMath0963.68147OpenAlexW2094783265MaRDI 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

zbMATH Keywords

circuit complexitydepth three Boolean circuits

Mathematics Subject Classification ID

Theory of computing (68Q99)

Related Items (7)

Subset sum ``cubes and the complexity of primality testing ⋮ The complexity of depth-3 circuits computing symmetric Boolean functions ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits ⋮ Unnamed Item ⋮ Parity helps to compute majority ⋮ The Complexity of Satisfiability of Small Depth Circuits

This page was built for publication: Exponential lower bounds for depth three Boolean circuits