Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Lower Bounds for Circuits with Few Modular and Symmetric Gates
verfasst von : Arkadev Chattopadhyay, Kristoffer Arnsfelt Hansen
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider constant depth circuits augmented with few modular, or more generally, arbitrary symmetric gates. We prove that circuits augmented with
o
(log
2
n
) symmetric gates must have size
n
$^{\Omega({\rm log}\ {\it n})}$
to compute a certain (complicated) function in
ACC
0
.
This function is also hard on the average for circuits of size
n
$^{\epsilon log {\it n}}$
augmented with
o
(log
n
) symmetric gates, and as a consequence we can get a pseudorandom generator for circuits of size
m
containing
$o(\sqrt{{\rm log} \ m})$
symmetric gates.
For a composite integer
m
having
r
distinct prime factors, we prove that circuits augmented with
s
MOD
m
gates must have size
${\it n}^{\Omega(\frac{1}{s}{\rm log}^{\frac{1}{r-1}}n)}$
to compute MAJORITY or MOD
l
, if
l
has a prime factor not dividing
m
. For proving the latter result we introduce a new notion of representation of boolean function by polynomials, for which we obtain degree lower bounds that are of independent interest.