ECCC-Report TR06-079https://eccc.weizmann.ac.il/report/2006/079Comments and Revisions published for TR06-079en-usWed, 21 Jun 2006 19:51:48 +0300
Paper TR06-079
| Lower Bounds for Circuits with Few Modular Gates using Exponential Sums |
Kristoffer Arnsfelt Hansen
https://eccc.weizmann.ac.il/report/2006/079 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.
Wed, 21 Jun 2006 19:51:48 +0300https://eccc.weizmann.ac.il/report/2006/079