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

DOI10.1007/978-3-030-43662-9_6MaRDI QIDQ5098770zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 3461412 (Why is no real title available?)
• scientific article; zbMATH DE number 3482343 (Why is no real title available?)
• scientific article; zbMATH DE number 3597878 (Why is no real title available?)
• A survey of lower bounds for satisfiability and related problems.
• Boolean function complexity. Advances and frontiers.
• Communication Complexity
• Complexity Lower Bounds using Linear Algebra
• Computational Complexity
• Fourier and circulant matrices are not rigid
• Hardness Amplification Proofs Require Majority
• Hardness vs randomness
• Lower bounds and separations for constant depth multilinear circuits
• Lower bounds on arithmetic circuits via partial derivatives
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Matrix rigidity of random Toeplitz matrices
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Parity, circuits, and the polynomial-time hierarchy
• Pseudorandom bits for constant depth circuits
• Random oracles separate PSPACE from the polynomial-time hierarchy
• Relationships between nondeterministic and deterministic tape complexities
• Tensor-rank and lower bounds for arithmetic formulas
• Top-down lower bounds for depth-three circuits
• \(\Sigma_ 1^ 1\)-formulae on finite structures

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)