[Colloquium] Talk by Mihai Patrascu, MIT on March 10, 2008

[caseyk]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Monday, March 10, 2007
Time: 2:30 p.m.
Place: Ryerson 251, 1100 E. 58th Street

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

Speaker:	Mihai Patrascu

From:		MIT

Web page:	http://web.mit.edu/~mip/www/

Title: Limits of Data Structure

Abstract:	 Over the years, theoretical computer science has been  
vastly more successful at producing positive results (algorithms,  
reductions) than negative ones ("SAT cannot be solved in polynomial  
time"). In fact, our understanding of lower bounds is so limited that,  
until recently, we failed to show:

* any Omega(lg n) lower bound, matching trivial upper bounds via  
binary search trees.


* that a data structure of size O(n^100) is ever better than one of  
size O(n).

  In this talk, we prove such lower bounds by two simple, yet  
surprising ideas. These techniques have been used to understand  
several central problems (such as IP lookup in Internet routers), and  
answer open questions dating back to 1989.

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

Host: Laci Babai