[Colloquium] THEORY TALK TODAY: Arkadev Chattopadhyay

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Tuesday, November 16, 2010 
Time: 3:00 p.m.
Place: Ryerson 251, 1100 E. 58th Street

----------------------------------------------

Speaker:		Arkadev Chattopadhyay

From:		University of Toronto

Web page:	http://www.cs.toronto.edu/~arkadev/

Title: 		Linear systems over arbitrary moduli

Abstract:  	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 <= i <= 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.

Refreshments will be served prior to the talk at 2:30 in Ryerson 255.