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

DOI10.1007/978-3-642-03351-3_13zbMATH Open1248.94132OpenAlexW1480920869MaRDI QIDQ3392947FDOQ3392947

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/

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

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

Cited In (4)

• Reducing the Depth of Quantum Circuits Using Additional Circuit Lines
• Depth reduction for composites
• Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms
• 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)