December 28, Monday
14:00 – 16:00
Analyzing Data Structures with Forbidden 0-1 Matrices
Computer Science seminar
Lecturer : Seth Pettie
Affiliation : Department of EECS University of Michigan Ann Arbor
Location : 202/37
Host : Dr. Michael Elkin
In this talk I'll exhibit a simple method for analyzing dynamic data
structures using various forbidden substructure theorems. The idea is
to (1) transcribe the behavior of the data structure as some kind of
combinatorial object, (2) show that the object does not contain some
forbidden substructure, and (3) bound the size of any such object
without this substructure. I'll show how to analyze path
compression-based data structurses using forbidden 0/1 submatrices,
then discuss some extremal problems on 0-1 matrices.
This talk covers results from two papers to appear in SODA 2010.