Advertisement
Published in:
2005 | OriginalPaper | Chapter
Lower Bounds for Circuits with Few Modular and Symmetric Gates
Authors : Arkadev Chattopadhyay, Kristoffer Arnsfelt Hansen
Published in: Automata, Languages and Programming
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.