[Colloquium] Talk by Emanuele Viola, Columbia University on Monday, February 11, 2008

[Nita Yack]

DEPARTMENT OF COMPUTER SCIENCE - TALK

SPONSORED BY UNIVERSITY OF CHICAGO

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

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

Speaker:  Emanuele Viola

From:	Columbia University

Web page:  http://www1.cs.columbia.edu/~viola/

Title: Lower Bounds and the Power of Randomness

Abstract:  Computation is an ubiquitous phenomenon in nature, and of  
increasing relevance to many fields such as economics, biology, and  
mathematics. In this talk we survey some of our results in two  
surprisingly interrelated areas that are central to the understanding  
of computation: lower bounds and the power of randomness.

In particular, we consider the fundamental problem of following a path  
in a graph whose edges are distributed among several collaborating  
players. We obtain a lower bound on the amount of communication that  
the players need to exchange, answering a decade-old question. We also  
consider the problem of constructing sequences of bits that ``look  
random'' though being generated with little or no randomness. Here we  
present a pseudorandom generator that stretches few random bits into a  
long sequence which looks random to polynomials. Our result marks the  
first progress on this problem since 1993, and has spurred interaction  
between computer scientists and mathematicians, leading to advances on  
an outstanding conjecture in combinatorics.

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

Host:  Laci 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/20080205/7d4fa7f9/attachment.html