Top-down lower bounds for depth-three circuits

DOI10.1007/BF01268140zbMath0838.68056OpenAlexW2079175807WikidataQ56959102 ScholiaQ56959102MaRDI QIDQ1904663

Pavel Pudlák, Johan T. Håstad, Stasys P. Jukna

Publication date: 7 January 1996

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01268140

zbMATH Keywords

computational complexitysmall-depth circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (14)

The complexity of depth-3 circuits computing symmetric Boolean functions ⋮ A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time ⋮ On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions ⋮ A degree version of the Hilton-Milner theorem ⋮ Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\) ⋮ Extremal problems in hypergraph colourings ⋮ Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation ⋮ String Matching: Communication, Circuits, and Learning. ⋮ Some structural properties of low-rank matrices related to computational complexity ⋮ Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates ⋮ The Cayley isomorphism property for Cayley maps ⋮ Coloring cross-intersecting families ⋮ Prediction from partial information and hindsight, with application to circuit lower bounds ⋮ Unnamed Item

Cites Work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• On lower bounds for read-\(k\)-times branching programs
• Intersection Theorems for Systems of Sets
• Parity, circuits, and the polynomial-time hierarchy
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth

This page was built for publication: Top-down lower bounds for depth-three circuits