[Colloquium] Talk by Andrej Bogdanov, Tsinghua University, on Monday, February 4, 2008-Correction

[Nita Yack]

DEPARTMENT OF COMPUTER SCIENCE - TALK

SPONSORED BY UNIVERSITY OF CHICAGO

Date: Monday, February 4, 2008
Time: 2:30 p.m.
Place: Ryerson 251, 1100 E. 58th St.

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

Speaker:  Andrej Bogdanov

From:	Tsinghua University

Web page:  http://itcs.tsinghua.edu.cn/postdoc/andrej.html

Title: Pseudorandom bits for polynomials

Abstract: Despite our general belief that randomized computations can  
be simulated deterministically in an efficient way, there are  
relatively few models for which results of this type can be shown  
unconditionally. On the other hand, the study of derandomization in  
simple models of computation has proved fruitful even in domains where  
no applications were apparent at the outset.



We consider pseudorandom generators for the class of low-degree  
multivariate polynomials over a finite field. For degree 1 polynomials  
(linear functions), such pseudorandom generators were first  
constructed by Naor and Naor in 1989 and have been widely studied and  
used ever since. In this talk we will discuss some recent progress in  
constructing pseudorandom generators for higher degree polynomials,  
and connections with other problems in computational complexity and  
arithmetic combinatorics.

  ****************************

Host:  Laszlo Babai





***********************************************************************************************************************************

Nita

**************************
Nita Yack
Departmental Administrator
Computer Science Department
1100 E. 58th Street - Room 151
Chicago, IL 60637
(773) 702-6019
(773) 702-8487 FAX

"Hard work spotlights the character of people: some turn up their  
sleeves, some turn up their noses, and some don't turn up at all."


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20080129/f2ce0738/attachment-0001.html