TR06-079 Authors: Kristoffer Arnsfelt Hansen

Publication: 21st June 2006 19:51

Downloads: 2827

Keywords:

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.