Depth Reduction for Circuits with a Single Layer of Modular Counting Gates

DOI10.1007/978-3-642-03351-3_13MaRDI QIDQ3392947zbMATH OpenOpenAlexFDO

Authors Kristoffer Arnsfelt Hansen

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/

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Lower bounds for modular counting by circuits with modular gates
• Lower bounds for modular counting by circuits with modular gates
• Depth reduction for circuits of unbounded fan-in
• On the computational power of depth 2 circuits with threshold and modulo gates
• On the computational power of depth-2 circuits with threshold and modulo gates

Cites work

• A note on \(\mathbf{MOD}_{p}\)-\(\mathbf{MOD}_{m}\) circuits
• A note on the power of majority gates and modular gates
• A weight-size trade-off for circuits with MOD \(m\) gates
• Automata, Languages and Programming
• Depth reduction for circuits of unbounded fan-in
• Harmonic Analysis of Polynomial Threshold Functions
• scientific article; zbMATH DE number 1301088 (Why is no real title available?)
• Lower Bounds for (MOD_p - MOD_m) Circuits
• Lower bounds for modular counting by circuits with modular gates
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Non-uniform automata over groups
• NP is as easy as detecting unique solutions
• On ACC
• On Graph Complexity
• On the computational power of depth-2 circuits with threshold and modulo gates
• On the power of small-depth threshold circuits
• Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
• Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
• Upper and lower bounds for some depth-3 circuit classes

Cited in

(6)

• Depth reduction for circuits of unbounded fan-in
• Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms
• Reducing the Depth of Quantum Circuits Using Additional Circuit Lines
• scientific article; zbMATH DE number 1129497 (Why is no real title available?)
• Depth reduction for composites
• Weights of exact threshold functions

This page was built for publication: Depth Reduction for Circuits with a Single Layer of Modular Counting Gates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3392947)