Linear-size constant-depth polylog-threshold circuits

DOI10.1016/0020-0190(91)90110-4zbMath0735.68035OpenAlexW1998480106MaRDI QIDQ1182085

Prabhakar Ragde, Avi Wigderson

Publication date: 27 June 1992

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(91)90110-4

zbMATH Keywords

threshold circuitsconstant-depth circuits\(AC^ 0\)approximate compaction

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (7)

Randomness buys depth for approximate counting ⋮ Circuit complexity of regular languages ⋮ Identification of partial disjunction, parity, and threshold functions ⋮ The Complexity of Propositional Proofs ⋮ Fine-Grained Cryptography ⋮ Unnamed Item ⋮ Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC

Cites Work

• Unnamed Item
• Bounded-depth, polynomial-size circuits for symmetric functions
• Unbounded fan-in circuits and associative functions
• Constant Depth Reducibility
• Definability by constant-depth polynomial-size circuits
• Bounds to Complexities of Networks for Sorting and for Switching

This page was built for publication: Linear-size constant-depth polylog-threshold circuits