18:00-- | Reception |
08:30--08:40 | Opening | |
Kazuo Iwama (Kyoto University) | ||
08:40--09:30 | Session 1 | |
``Fast and Sensitive Homology Search''
Ming Li (University of Waterloo) |
||
09:30--10:20 | Session 2 | |
``Dynamic graph algorithms with applications''
Mikkel Thorup (AT&T) |
||
10:20--10:40 | Coffee break | |
10:40--11:30 | Session 3 | |
``Approximation Algorithms for Stochastic Combinatorial Optimization''
R. Ravi (Carnegie Mellon University) |
||
11:30--12:20 | Session 4 | |
``More approximation algorithms for stochastic programming problems''
David Shmoys (Cornell University) |
||
12:20--14:00 | Lunch break | |
14:00--15:00 | Free Discussion | |
15:00--15:50 | Session 5 | |
``Efficient Haplotype Inference on Pedigrees and
Applications in Gene Association Mapping''
Tao Jiang (UC Riverside) |
||
15:50--16:10 | Coffee break | |
16:10--17:00 | Session 6 | |
``New Horizons in Machine Learning''
Avrim Blum (Carnegie Mellon University) |
||
17:00--17:50 | Session 7 | |
``Rigorous Analysis of Heuristics for NP-hard Problems''
Uriel Feige (Weizmann Institute) |
||
17:50--18:00 | Break | |
18:00-- | Conference dinner |
08:40--09:30 | Session 11 | |
``Algorithms for Modern Memory Systems''
Martin Farach-Colton (Rutgers University) |
||
09:30--10:20 | Session 12 | |
``Data Stream Algorithms and Applications''
Shan Muthukrishnan (Rutgers University) |
||
10:20--10:40 | Coffee break | |
10:40--11:30 | Session 13 | |
``On Computing all Abductive Explanations from
a Propositional Horn Theory''
Kazuhisa Makino (Osaka University) |
||
11:30--12:20 | Session 14 | |
``How to Influence Noncooperative, Selfish Agents''
Lisa Fleischer (IBM) |
||
12:20--14:00 | Lunch break | |
14:00--16:00 | Free Discussion | |
16:00--16:50 | Session 15 | |
``Metric Labeling: Upper and Lower Bounds''
Seffi Naor (Technion) |
||
16:50--17:40 | Session 16 | |
``Approximate distance oracles and spanners with
sublinear error terms''
Uri Zwick (Tel-Aviv University) |
20:00-- | Business Meeting |
08:40--09:30 | Session 17 | |
``The walkers problem: On the cycle and the grid''
Josep Diaz (Universitat Politecnica de Catalunya) |
||
09:30--10:20 | Session 18 | |
``Connectivity and information transfer in social networks''
Richard Cole (New York University) |
||
10:20--10:40 | Coffee break | |
10:40--11:30 | Session 19 | |
``Approximation Algorithms for Network Problems''
Susanne Albers (University of Freiburg) |
||
11:30--12:20 | Session 20 | |
``Generalized linear programming''
Jiri Matousek (Charles University) |
||
12:20--14:00 | Lunch break | |
14:00--14:50 | Session 21 | |
``My Favorite Ten Complexity Theorems of the Past Decade II''
Lance Fortnow (University of Chicago) |
||
14:50--15:40 | Session 22 | |
``Some Heuristic Analysis of
Average Behavior of Local Search Algorithms''
Osamu Watanabe (Tokyo Institute of Technology) |