NHC Program

February 27 (Sunday)

18:00-- Reception

February 28 (Monday)

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

March 1 (Tuesday)

08:40--09:30 Session 8
``Data Stream Algorithms in Computational Geometry''
Timothy Chan (University of Waterloo)
09:30--10:20 Session 9
``Steps into Computational Algebraic Topology''
Herbert Edelsbrunner (Duke University)
10:20--10:40 Coffee break
10:40--12:00 Session 10: Short talks in parallel sessions
Session 10-A Session 10-B
``Efficient Algorithms for the Longest Path Problem''
Ryuhei Uehara (JAIST) 		``Site-oriented Framework for Mining Communities on the Web''
Yasuhiro Asano (Tohoku University)
``Improved Approximation Algorithms for Metric Max TSP''
Z.Z. Chen (Tokyo Denki University) 		``On Right-Hand-on-the-Wall Traversal of Graphs''
Kunihiko Sadakane (Kyushu University)
``Proposal of Asynchronous Distributed Branch and Bound''
Atsushi Sasaki, Tadashi Araragi (NTT CSL), * Shigeru Masuyama (Toyohashi University of Technology) 		``Distributing Distinct Integers Uniformly over a Square Matrix with Application to Digital Halftoning''
Tetsuo Asano (JAIST)
``Energy-Optimal Online Algorithms for Broadcasting in Wireless Networks''
Hirotaka Ono (Kyushu University) 		``Ultimate Implementation and Analysis of the AMO Algorithm for Pricing European-Asian Options''
Akiyoshi Shioura (Tohoku University)
12:00--13:20 Lunch Break
13:20-- Excursion (Walking Kyoto tour)

March 2 (Wednesday)

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

March 3 (Thursday)

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)