| DATE |
SPEAKER |
TITLE
(link to abstracts) |
Notes |
| Jan 25 |
|
|
SODA. |
| Feb 1 |
Asaf Shapira |
Every Monotone
Graph Property is Testable
|
Core 433 |
| Feb 8 |
Rocco A. Servedio |
Learning
decision trees and DNF formulas in the average case
|
|
| Feb 15 |
Gopal Pandurangan |
Nearest
Neighbor Trees and their Algorithmic Applications
|
|
| Feb 22 |
Moses Charikar |
Aggregating
inconsistent information: Ranking and Clustering
|
|
| Mar 1 |
Martin Pal |
Stochastic
Steiner tree without the root
|
Core 433; Muthu away |
| Mar 8 |
Yury Makarychev |
O(\sqrt{log
n}) approximation algorithms for Min UnCut, Min 2CNF Deletion, and directed
cut problems
|
Core 433 |
|
Mar 15 |
SPRING RECESS |
SPRING RECESS |
|
| Mar 22 |
Konstantin Makarychev |
Quadratic
forms on graphs
|
Core 229
UNUSUAL ROOM |
| Mar 29 |
Guy Kindler |
New explicit
constructions of randomness extractors from weak
sources, and of bipartite Ramsey graphs.
|
|
| Apr 05 |
Mike Saks
|
Every boolean
decision tree has an influential variable
|
|
| Apr 12 |
Mario Szegedy |
Near optimality
of the priority sampling procedure
|
|
| Apr 19 |
M. Alekhnovitch
|
Hardness
of Approximating the Closest Vector Problem with Pre-Processing
|
|
| Apr 26 |
Sanjeev Khanna |
New Algorithms
and Hardness Results for Disjoint Paths Problem
|
|
| May 3 |
Sudipto Guha
|
Have epsilons
helped you lately? Algorithmic impact on
Histogram & Wavelet construction problems
|
|
May 26
THURS |
Seth Pettie
|
Approximating
Shortest Paths with Purely Additive Spanners
|
Host: Farach-Colton
|