Depth reduction for circuits of unbounded fan-in

DOI10.1006/inco.1994.1057zbMath0820.68046OpenAlexW2075848688MaRDI QIDQ1333269

Ulrich Hertrampf, Eric W. Allender

Publication date: 13 September 1994

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/700f3ba7517a79f8a4330bd3b878169becbf01fb

zbMATH Keywords

constant depth circuitsdepth reduction theorems

Mathematics Subject Classification ID

Related Items (16)

When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one ⋮ Perceptrons, PP, and the polynomial hierarchy ⋮ On ACC ⋮ Uniform proofs of ACC representations ⋮ Upper and lower bounds for some depth-3 circuit classes ⋮ Collapsing modular counting in bounded arithmetic and constant depth propositional proofs ⋮ Depth Reduction for Composites ⋮ A note on the power of majority gates and modular gates ⋮ A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem] ⋮ Depth Reduction for Circuits with a Single Layer of Modular Counting Gates ⋮ Non-commutative arithmetic circuits: depth reduction and size lower bounds ⋮ Relating polynomial time to constant depth ⋮ Derandomizing Isolation in Space-Bounded Settings ⋮ On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits ⋮ Quantum neural networks ⋮ On learning embedded midbit functions

This page was built for publication: Depth reduction for circuits of unbounded fan-in