[Colloquium] Reminder: Talk by Mihai Patrascu, MIT Today

[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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20080310/38e6a6cf/attachment.html