## Speaker:

## Time:

## Venue:

- A-212 (STCS Seminar Room)

Our work extends the recent result of Chattopadhyay and Wigderson (FOCS'09) who obtain such a correlation bound for linear systems over cyclic groups whose order is a product of two distinct primes or has at most one prime factor. Our result also immediately yields the first exponential bounds on the size of boolean depth-three circuits of the form $\\text{MAJ} \\circ \\text{AND} \\circ \\text{MOD}_m^A$ for computing the $\\text{MOD}_q$ function, when $m,q$ are co-prime. No superpolynomial lower bounds were known for such circuits for computing any explicit function, when $m$ had three or more distinct prime factors.

This completely solves an open problem posed by Beigel and Maciel (Complexity'97) (this is joint work with Shachar Lovett, IAS-Princeton).