Theory Seminar (CSE 590Z)

Spring 2001

The seminar meets in EE1 037, Tuesdays at 1:30 pm.

Month Day Speaker Title
March 27 Brian Tjaden Approximate Max-Flow Min(multi)-Cut Theorems, by Garg, Vazirani and Yannakakis
April 3 Matt Cary and Erik Vee Total Unimodularity
April 10 Alex Lopez-Ortiz A Linear Time and Space Lower Bound for the String Matching Problem
April 17 Karim Filali "Worst-case equilibria", by Koutsoupias and Papadimitriou
April 24 Mike Mitzenmacher Compressed Bloom Filters and Compressing the Web Graph
May 1 Jason Hartline "Algorithmic Mechanism Design" by Nisan and Ronen
May 7 Christos Papadimitriou The Complexity of Tradeoffs
May 8 Yuriy A. Reznik Preliminary Analysis of Tries with Adaptive Multi-Digit Branching
May 15 Justin Campbell Property Testing
May 22 T.S. Jayram Benefit task systems with applications to online allocation of servers in a web server farm
May 25 David Zuckerman Extractors, Codes, and Unbalanced Expanders
May 29 Dana Randall Decomposition, Swapping and Mean-Field Models


Trends in UW Theory (CSE 590ZZ)

Spring 2001

This is a seminar in which UW theory students and faculty present their ongoing research in an informal setting. It meets in MGH 242 Wednesdays at 3:30 pm.

Month Day Speaker Subjects
April 4 Frank McSherry Spectral Partitioning of Random Graphs
April 11 Dimitris Achlioptas Database Friendly Random Projections
April 18 Jared Saia Flow Routing
April 25 Eric Anderson "How Bad is Selfish Routing?", by Roughgarden and Tardos
May 2 Paul Beame A Sharp Threshold in Proof Complexity
May 9 Amos Fiat Web Search via Hub Synthesis
May 16 Matt Cary Pairwise Independence
May 23 Kenneth Tam Parallel Processor Scheduling with Delay Constraints, by D Engels, J Feldman, D Karger, M Ruhl
May 30 Ashish Sabarwal "Matching is as Easy as Matrix Inversion" by K. Mulmuley, U. Vazirani and V. Vazirani

CSE 590z home