Eastern Great Lakes Theory Workshop Talk

Linear Systems over Composite Moduli

Arkadev Chattopadhyay, University of Toronto

Sunday, October 10, 10:30am-11:30am

ABSTRACT

Consider systems of 'generalized' linear equations of the following form in n variables over Z_m, where m is a fixed composite number like 6:

l_1(x_1,...,x_n) in A_1,...,l_t(x_1,...,x_n) in A_t,

where each A_i is an arbitrary subset of Z_m. We show that the set of points of the boolean cube that satisfy any such system looks extremely pseudorandom to a MOD_q counter, if m and q are co-prime, i.e the solution set has exponentially small correlation with the boolean function MOD_q. This solves an open problem of Beigel and Maciel, and yields some progress on understanding the computational power of constant-depth circuits having MOD_m gates.

Our technique combines ideas involving matrix rigidity from the work of Grigoriev and Razborov with Bourgain's estimates of certain exponential sums.

Based on two works, the first joint with Avi Wigderson and the second with Shachar Lovett.

Slides

Speaker Bio

Arkadev grew up mostly in a small mining town called Dalli-Rajhara in Chattisgarh, India. He got his undergraduate degree from the Indian Institute of Technology, Kharagpur in Electronics and Electrical Communication Engineering in 1994. Then, he spent eight years in the software industry, first in Kolkata, India and later in Montreal, Canada where he managed projects for telecommunications applications.

Somewhat accidentally, he started his graduate studies in Computer Science at McGill University from 2002 and earned his Ph.D from there in 2008. He was a member at the Institute for Advanced Study, Princeton in 2008-2009 in the School of Mathematics and has been a postdoctoral fellow at the University of Toronto since September, 2009. His research interests are in theoretical computer science.

< Schedule < EaGL-III homepage