On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions

DOI10.1007/978-3-030-43662-9_6OpenAlexW2408001118MaRDI QIDQ5098770

Oded Goldreich, Avi Wigderson

Publication date: 30 August 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.642.2310

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds and separations for constant depth multilinear circuits
• Boolean function complexity. Advances and frontiers.
• Pseudorandom bits for constant depth circuits
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Random oracles separate PSPACE from the polynomial-time hierarchy
• Hardness vs randomness
• Lower bounds on arithmetic circuits via partial derivatives
• Matrix rigidity of random Toeplitz matrices
• Top-down lower bounds for depth-three circuits
• Relationships between nondeterministic and deterministic tape complexities
• Tensor-rank and lower bounds for arithmetic formulas
• Parity, circuits, and the polynomial-time hierarchy
• Complexity Lower Bounds using Linear Algebra
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• A Survey of Lower Bounds for Satisfiability and Related Problems
• Communication Complexity
• Fourier and circulant matrices are not rigid
• Hardness Amplification Proofs Require Majority
• Computational Complexity

This page was built for publication: On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions