Lower Bounds for Circuits with Few Modular Gates using Exponential Sums

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Department of Computer Science
  • Teoretisk naturvidenskab
We prove that any AC0 circuit augmented with {epsilon log2 n} MODm gates and with a MAJORITY gate at the output, require size nOmega(log n) to compute MODl, when l has a prime factor not dividing m and epsilon is sufficiently small. We also obtain that the MOD2 function is hard on the average for AC0 circuits of size nepsilon log n augmented with {epsilon log2 n} MODm 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 MOD2 function, for circuits of size S containing epsilon log S MODm gates. Our results are based on recent bounds of exponential sums that were previously introduced for proving lower bounds for MAJ o MODm o ANDd circuits.
Original languageEnglish
JournalElectronic Colloquium on Computational Complexity
Number of pages8
Publication statusPublished - 2006

See relations at Aarhus University Citationformats

ID: 3630525