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
Date: 
Apr 15, 2008 11:00am - 12:00pm

There is a sign up schedule for this event:
htt

p://www.cs.utexas.edu/department/webevent/utcs/events/cgi/list_events.cgi
Type of Talk: UTCS Colloquium/FACULTY CANDIDATE

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

ting
back to 1989.