Abstract:
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.