Upper and lower bounds for some depth-3 circuit classes
From MaRDI portal
(Redirected from Publication:1377575)
Recommendations
- Top-down lower bounds for depth-three circuits
- A lower bound for depth-3 circuits with MOD m gates
- Exponential size lower bounds for some depth three circuits
- Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates
- Lower bounds for depth-three circuits with equals and Mod-gates
- Approximate degree and the complexity of depth three circuits
- Exponential lower bounds for depth three Boolean circuits
- Multi-k-ic depth three circuit lower bound
- Multi-\(k\)-ic depth three circuit lower bound
- scientific article; zbMATH DE number 1559525
Cites work
- A guided tour of Chernoff bounds
- A note on a theorem of Barrington, Straubing and Thérien
- A note on the power of majority gates and modular gates
- A weight-size trade-off for circuits with MOD \(m\) gates
- An oracle separating \(\oplus P\) from \(PP^{PH}\)
- Circuits constructed with MOD\(_ q\) gates cannot compute ``and in sublinear size
- Depth reduction for circuits of unbounded fan-in
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Non-uniform automata over groups
- On ACC
- On the computational power of depth-2 circuits with threshold and modulo gates
- On the power of small-depth threshold circuits
- Parity, circuits, and the polynomial-time hierarchy
- Representing Boolean functions as polynomials modulo composite numbers
- Some notes on threshold circuits, and multiplication in depth 4
- Threshold circuits of bounded depth
- Threshold circuits of small majority-depth
- When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
Cited in
(17)- A nonuniform circuit class with multilayer of threshold gates having super quasi polynomial size lower bounds against NEXP
- scientific article; zbMATH DE number 6789296 (Why is no real title available?)
- scientific article; zbMATH DE number 1559525 (Why is no real title available?)
- Exponential lower bound for bounded depth circuits with few threshold gates
- Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates
- Size and Energy of Threshold Circuits Computing Mod Functions
- Depth Reduction for Circuits with a Single Layer of Modular Counting Gates
- On small depth threshold circuits
- Top-down lower bounds for depth-three circuits
- Powering requires threshold depth 3
- On the correlation between parity and modular polynomials
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- The correlation between parity and quadratic polynomials mod \(3\)
- Exponential size lower bounds for some depth three circuits
- A lower bound for depth-3 circuits with MOD \(m\) gates
- Approximate degree and the complexity of depth three circuits
- On \(\mathrm{TC}^{0}\) lower bounds for the permanent
This page was built for publication: Upper and lower bounds for some depth-3 circuit classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1377575)
