Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-079 | 12th June 2006 00:00

Lower Bounds for Circuits with Few Modular Gates using Exponential Sums


Authors: Kristoffer Arnsfelt Hansen
Publication: 21st June 2006 19:51
Downloads: 1123


We prove that any AC0 circuit augmented with {epsilon log^2 n}
MOD_m gates and with a MAJORITY gate at the output, require size
n^{Omega(log n)} to compute MOD_l, when l has a prime
factor not dividing m and epsilon is sufficiently small. We
also obtain that the MOD_2 function is hard on the average for
AC0 circuits of size n^{epsilon log n} augmented with
{epsilon log^2 n} MOD_m gates, for every odd integer m and
any sufficiently small epsilon. As a consequence, for every
odd integer m, we obtain a pseudorandom generator, based on the
MOD_2 function, for circuits of size S containing epsilon
log S MOD_m gates.

Our results are based on recent bounds of exponential sums that were
previously introduced for proving lower bounds for
MAJ o MOD_m o AND_d circuits.

ISSN 1433-8092 | Imprint