Speaker/Affil

iation: Mihai Patrascu/Massachusetts Institute of Technology

Date/T

ime: Tuesday April 15 2008 11:00 a.m.

Location: ACES 2.302
<

br>Host: Anna Gal

Talk Title: Limits of Data Structures

Tal

k Abstract:
Over the years theoretical computer science has been vastly

more successful at producing positive results (algorithms
reducti

ons) than negative ones (SAT cannot be solved in
polynomial time). In f

act our understanding of lower bounds
is so limited that until recent

ly we failed to show:

* any Omega(lg n) lower bound matching trivi

al upper bounds
via binary search trees.

* that a data structure
of size O(n%5E100) is ever better than one
of size O(n).

In thi

s talk we prove such lower bounds by two simple yet
surprising ideas.
These techniques have been used to
understand several central problem

s (such as IP lookup
in Internet routers) and answer open questions da