Upper and lower bounds for some depth-3 circuit classes
From MaRDI portal
Publication:1377575
DOI10.1007/BF01294257zbMath0890.68063MaRDI QIDQ1377575
Publication date: 6 July 1998
Published in: Computational Complexity (Search for Journal in Brave)
Related Items (4)
The correlation between parity and quadratic polynomials mod \(3\) ⋮ Size and Energy of Threshold Circuits Computing Mod Functions ⋮ On the correlation between parity and modular polynomials ⋮ Depth Reduction for Circuits with a Single Layer of Modular Counting Gates
Cites Work
- A note on the power of majority gates and modular gates
- On the power of small-depth threshold circuits
- An oracle separating \(\oplus P\) from \(PP^{PH}\)
- Non-uniform automata over groups
- A guided tour of Chernoff bounds
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Some notes on threshold circuits, and multiplication in depth 4
- On the computational power of depth-2 circuits with threshold and modulo gates
- Threshold circuits of small majority-depth
- Depth reduction for circuits of unbounded fan-in
- When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
- On ACC
- Representing Boolean functions as polynomials modulo composite numbers
- Circuits constructed with MOD\(_ q\) gates cannot compute ``and in sublinear size
- A note on a theorem of Barrington, Straubing and Thérien
- \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
- Threshold circuits of bounded depth
- A weight-size trade-off for circuits with MOD m gates
- Parity, circuits, and the polynomial-time hierarchy
This page was built for publication: Upper and lower bounds for some depth-3 circuit classes
