UTCS FACULTY CANDIDATE: Mihai Patrascu/Massachusetts Institute of Technology Limits of Data Structures ACES 2.302 Tuesday April 15 2008 11:00 a.m.

Contact Name: 
Jenna Whitney
Apr 15, 2008 11:00am - 12:00pm

There is a sign up schedule for this event:

Type of Talk: UTCS Colloquium/FACULTY CANDIDATE


iation: Mihai Patrascu/Massachusetts Institute of Technology


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

Location: ACES 2.302

br>Host: Anna Gal

Talk Title: Limits of Data Structures


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

more successful at producing positive results (algorithms

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

back to 1989.