[Colloquium] CANCELLLED: Arkadev Chattapadhyay Talk on November 17th

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Tuesday, November 17, 2009
Time: 3:00 p.m.
Place: RY 251

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

Speaker:	Arkadev Chattapadhyay

From:		University of Toronto

Website: 	http://www.cs.mcgill.ca/~achatt3/

Title: 	 Linear systems over composite moduli

Abstract:  We study solution sets to systems of 'generalized' linear  
equations of the form \ell_i (x_1, x_2,..., x_n) \in A_i  (mod m)  
where \ell_1,...,\ell_t are linear forms in n Boolean variables, each  
A_i is an arbitrary subset of Z_m, and m is a composite integer that  
is a product of two distinct primes, like 6. Our main technical result  
is that such solution sets have exponentially small correlation, i.e.  
\exp(-\Omega(n)), with the boolean function MOD_q, when m and q are  
relatively prime. This bound is independent of the number t of  
equations.

This yields  progress on limiting the power of constant-depth circuits  
with modular gates. We derive the first exponential lower bound on the  
size of depth-three circuits of type MAJ of AND of MOD_m^A (i.e.  
having a MAJORITY gate at the top, AND/OR gates at the middle layer  
and generalized MOD_m gates at the base) computing the function MOD_q.  
This settles an open problem of Beigel and Maciel (Complexity'97), for  
the case of such modulus m.

Our technique makes use of the work of Bourgain (2005) on estimating  
exponential sums involving a low-degree polynomial and ideas involving  
matrix rigidity from the work of Grigoriev and Razborov (FOCS'98) on  
'arithmetic circuits' over finite fields.


Refreshments will be held in RY 255 prior to the talk at 2:30.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20091116/9d1525d4/attachment.htm