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

[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

Abstract:  Efficient 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  
about proving lower bounds, i.e. establishing that some explicit  
functions cannot be computed with limited resources. We explore  
various resources such as communication, time, circuit depth, and  
randomness, highlighting surprising connections among them.


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  
exhibit lower bounds on the efficiency of error-correcting procedures,  
and present a recent result that formalizes the feeling that decoding  
is more difficult than encoding.
  ****************************

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/20080207/88e34c90/attachment-0001.html