SPEAKER: Arkadev Chattopadhyay, University
TITLE: Linear systems over arbitrary moduli
Consider a system of generalized linear equations over
Z_m of the following form: l_i(x_1,...,x_n) in A_i for 1 \leq i \leq t, where
each A_i is a subset of Z_m and m is a constant number like 6. We show that the
boolean solution set of such a system has exponentially small correlation with
the boolean MOD_q function, if m and q are co-prime. We obtain this result by
combining ideas involving matrix rigidity from Grigoriev and Razborov (FOCS 98)
with estimates of exponential sums by Bourgain (2005).
This immediately implies that depth-three circuits of
type Majority of AND of MOD_m^A need exponential size to compute the MOD_q
function. This is the first superpolynomial lower bound on the size of such circuits
and settles an open problem due to Beigel and Maciel (Complexity 97).
Based on two works, one joint with Avi Wigderson and the
other joint with Shachar Lovett.