On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions
From MaRDI portal
Publication:5098770
DOI10.1007/978-3-030-43662-9_6OpenAlexW2408001118MaRDI QIDQ5098770FDOQ5098770
Authors: Oded Goldreich, A. 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
Recommendations
- On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions
- The complexity of depth-3 circuits computing symmetric Boolean functions
- Exponential lower bounds for depth three Boolean circuits
- On realization complexity of linear Boolean transformations by schemes of depth 3
- scientific article; zbMATH DE number 1559525
- Approximating Boolean functions with depth-2 circuits
- On the complexity and depth of circuits that realize partial Boolean functions
- Exponential size lower bounds for some depth three circuits
- Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates
- scientific article; zbMATH DE number 1775446
Cites Work
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Hardness vs randomness
- Relationships between nondeterministic and deterministic tape complexities
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Title not available (Why is that?)
- Communication Complexity
- Computational Complexity
- Boolean function complexity. Advances and frontiers.
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Parity, circuits, and the polynomial-time hierarchy
- Pseudorandom bits for constant depth circuits
- Top-down lower bounds for depth-three circuits
- Lower bounds on arithmetic circuits via partial derivatives
- Complexity Lower Bounds using Linear Algebra
- Hardness Amplification Proofs Require Majority
- Lower bounds and separations for constant depth multilinear circuits
- Title not available (Why is that?)
- A survey of lower bounds for satisfiability and related problems.
- Title not available (Why is that?)
- Matrix rigidity of random Toeplitz matrices
- Tensor-rank and lower bounds for arithmetic formulas
- Random oracles separate PSPACE from the polynomial-time hierarchy
- Fourier and circulant matrices are not rigid
Cited In (4)
- On Computing Multilinear Polynomials Using Multi- r -ic Depth Four Circuits
- On the size of depth-two threshold circuits for the inner product mod 2 function
- On the VC-dimension of depth four threshold circuits and the complexity of Boolean-valued functions
- Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates
This page was built for publication: On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5098770)
