### DIMACS Theoretical Computer Science Seminar

Title: Linear Systems Over Finite Abelian Groups

Speaker: **Shachar Lovett**, Institute for Advanced Studies

Date: Wednesday, February 23, 2011 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

We consider a system of linear constraints in boolean variables over any finite
Abelian group $G$ of the following form: a linear equation is a constraint of the
form $a_1 x_1 + ... + a_n x_n \in A$, where the variables x_1,...,x_n are boolean,
the coefficients a_1,...,a_n are elements of G,
and A is a subset of G. A linear system is a set of linear constraints.
Our main result shows that the subset of the boolean cube that satisfies these constraints has exponentially small
correlation with the MOD_k boolean function, whenever the order of $G$ and $k$ are co-prime numbers.

Our work extends the result of Chattopadhyay and Wigderson (FOCS'09) who obtain such a correlation bound
when $G=Z_{pq}$ where $p,q$ are distinct prime factors. Our result yield the
first exponential bounds on the size of boolean depth-four circuits of the form MAJ - AND - ANY_{O(1)} - MOD_m^A
for computing the MOD_k function, when $m,k$ are co-prime.
No superpolynomial lower bounds were known for such circuits for computing any explicit function.

This completely solves an open problem posed by Beigel and Maciel (Complexity'97).
Joint work with Arkadev Chattopadhyay.