DagSemProc.08381.4.pdf
- Filesize: 211 kB
- 11 pages
Document
Depth Reduction for Circuits with a Single Layer of Modular Counting Gates
Author
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 8381
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2008-12-17
Cite As Get 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.
Subject Classification
Keywords
- Boolean Circuits
- Randomized Polynomials
- Fourier sums
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads