Depth Reduction for Circuits with a Single Layer of Modular Counting Gates
From MaRDI portal
Publication:3392947
DOI10.1007/978-3-642-03351-3_13zbMath1248.94132OpenAlexW1480920869MaRDI QIDQ3392947
Publication date: 18 August 2009
Published in: Computer Science - Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2008/1782/
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (3)
Weights of exact threshold functions ⋮ Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms ⋮ Depth Reduction for Composites
Cites Work
- Unnamed Item
- A note on the power of majority gates and modular gates
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
- On the power of small-depth threshold circuits
- Non-uniform automata over groups
- NP is as easy as detecting unique solutions
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- On the computational power of depth-2 circuits with threshold and modulo gates
- Depth reduction for circuits of unbounded fan-in
- On ACC
- Upper and lower bounds for some depth-3 circuit classes
- Lower bounds for modular counting by circuits with modular gates
- A note on \(\mathbf{MOD}_{p}\)-\(\mathbf{MOD}_{m}\) circuits
- A weight-size trade-off for circuits with MOD m gates
- On Graph Complexity
- Harmonic Analysis of Polynomial Threshold Functions
- Lower Bounds for (MODp - MODm) Circuits
- Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
- Automata, Languages and Programming
This page was built for publication: Depth Reduction for Circuits with a Single Layer of Modular Counting Gates
