Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates
From MaRDI portal
Recommendations
- Lower bounds for complexity of Boolean circuits of finite depth with arbitrary elements
- scientific article; zbMATH DE number 1559525
- Exponential lower bounds for depth three Boolean circuits
- The complexity of depth-3 circuits computing symmetric Boolean functions
- Upper and lower bounds for some depth-3 circuit classes
Cites work
- Boolean Circuits, Tensor Ranks, and Communication Complexity
- Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
- Communication in bounded depth circuits
- Entropy of operators or why matrix multiplication is hard for depth-two circuits
- scientific article; zbMATH DE number 5077418 (Why is no real title available?)
- scientific article; zbMATH DE number 3597878 (Why is no real title available?)
- Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
- On shifting networks
- Superconcentrators of depth 2
- Superconcentrators of depths 2 and 3; odd levels help (rarely)
Cited in
(16)- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Through the mincing machine with a Boolean layer cake: nonstandard computations over Boolean circuits in the lower-bounds-to-circuit-size complexity proving
- Lower bounds on the area complexity of Boolean circuits
- Upper and lower bounds for some depth-3 circuit classes
- The size and depth of layered Boolean circuits
- Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth
- \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
- A nonlinear lower bound for constant depth arithmetical circuits via the discrete uncertainty principle
- A lower bound for depth-3 circuits with MOD m gates
- Lower bounds for complexity of Boolean circuits of finite depth with arbitrary elements
- Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
- On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions
- scientific article; zbMATH DE number 7250166 (Why is no real title available?)
- Lower bounds for matrix product, in bounded depth circuits with arbitrary gates
- Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
- On shifting networks
This page was built for publication: Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3503631)
