[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

*REMINDER*

Theory Seminar

Today in Ryerson 251 @ 3 pm

Pooya Hatami
University of Chicago
www.cs.uchicago.edu
 
Title:  “Algorithmic Regularity for Polynomials and Applications”
 
Abstract: In analogy with the regularity lemma of Szemeredi, regularity lemmas for polynomials given by Green and Tao and by Kaufman and Lovett give a way of modifying a given collection F of  polynomials to a new collection F', so that the polynomials in the new collection are ``pseudorandom''.  These lemmas have various applications, such as (special cases) of Reed-Muller testing and worst-case to average-case reductions for polynomials. However, the transformation from F to F' is not algorithmic for either regularity lemma.
 
 
We define new notions of regularity for polynomials, which are analogous to the above, but allow for an efficient algorithm to compute the pseudorandom collection F'. We also prove that our notions suffice for the applications, for which the above regularity lemmas were proved.
 
Host: Prof. Alexander Razborov
 
*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*
 
 
 
 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20130521/a24a06a8/attachment.htm