Top-down lower bounds for depth-three circuits
From MaRDI portal
Publication:1904663
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
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
