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

Author Kristoffer Arnsfelt Hansen



PDF
Thumbnail PDF

File

DagSemProc.08381.4.pdf
  • Filesize: 211 kB
  • 11 pages

Document Identifiers

Author Details

Kristoffer Arnsfelt Hansen

Cite AsGet BibTex

Kristoffer Arnsfelt Hansen. Depth Reduction for Circuits with a Single Layer of Modular Counting Gates. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/DagSemProc.08381.4

Abstract

We consider the class of constant depth AND/OR circuits augmented with a layer of modular counting gates at the bottom layer, i.e ${AC}^0 circ {MOD}_m$ circuits. We show that the following holds for several types of gates $G$: by adding a gate of type $G$ at the output, it is possible to obtain an equivalent randomized depth 2 circuit of quasipolynomial size consisting of a gate of type $G$ at the output and a layer of modular counting gates, i.e $G circ {MOD}_m$ circuits. The types of gates $G$ we consider are modular counting gates and threshold-style gates. For all of these, strong lower bounds are known for (deterministic) $G circ {MOD}_m$ circuits.
Keywords
  • Boolean Circuits
  • Randomized Polynomials
  • Fourier sums

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail