UTCS FACULTY CANDIDATE: Mihai Patrascu/Massachusetts Institute of Technology Limits of Data Structures ACES 2.302 Tuesday April 15 2008 11:00 a.m.
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
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).
s talk we prove such lower bounds by two simple yet
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.
- Awards & Honors
- About Us
- Student Engagement and Support
- Masters Program
- Ph.D. Program
- Financial Information
- Prospective Students
- Incoming Students
- Current Students
- Curricular Practical Training
- Grad Student Talks
- UTCS Direct