Friday June 22

9:009:30 
Registration and Breakfast 
9:3010:00 
Ian Munro, University of Waterloo
A Worst Case Constant Time Priority Queue 
10:0510:35 
Jeff Edmonds, York University
TCP has Competitive Flow Times 
10:4011:10 
Jon Kleinberg, Cornell University
SmallWorld Phenomena and the Dynamics of Information 
11:1511:45 
Steven Rudich, Carnegie Mellon University
Formal Code Obfuscation 
11:5012:05 
TBA 
12:102:00 
Lunch

2:002:30 
Martin Tompa, University of Washington
Identifying Motifs in Orthologous DNA Sequences from Multiple
Species 
2:353:05 
David Kirkpatrick, University of British Columbia
Restructuring Ordered Binary Trees 
3:103:40 
Madhu Sudan, Massachusetts Institute of Technology
Random walks with "Back Buttons" 
3:454:15 
Coffee Break 
4:154:35 
C. C. Gotlieb, University of Toronto
"The New Real Estate" (Control of channels) 
4:405:10 
Panayiotis Tsaparas, University of Toronto
Link Analysis Ranking Algorithms on the World Wide Web 
5:155:45 
Adi Rosen, Technion
Tight Bounds on the Performance of LongestInSystem on DAGs



Saturday June 23

9:009:30
 A. A. Razborov, Steklov Mathematics Institute/IAS
Proof Complexity of Pigeonhole Principles 
9:3510:05 
Leslie Valiant, Harvard University
Quantum Computations that Can be Simulated Classically in Polynomial
Time 
10:0510:35 
Coffee Break 
10:3511:05 
Nicholas Pippenger, University of Bristish
Columbia
Random Boolean Functions 
11:1011:40 
Shai BenDavid, Technion
Computational Complexity vs. Statistical Generalization in Learning
 A survey of current knowledge and major questions 
11:4512:15 
Hisao Tamaki, Meiji University
Heuristic algorithms for Euclidean TSP based on Arora's dynamic
programming scheme 
12:152:00 
Lunch 
2:002:30 
Avi Wigderson, Institute for Advanced
Study
Expanders  where Combinatorics and Algebra compete and cooperate

2:353:05 
Eli Upfal, Brown University
Can Entropy Characterize Performance of Online Algorithms? 
3:103:40 
Baruch Schieber, IBM  T.J. Watson
Research Center
Online Server Allocation in a Server Farm via Benefit Task System

3:404:10 
Coffee Break

4:104:40 
Ran ElYaniv, Technion
On online learning of expert advice 
4:455:15 
Yuval Rabani, Technion
Geometric Search Structures in High Dimensional Spaces 
5:205:50 
Rafail Ostrovsky, Telcordia Technologies
NonInteractive and NonMalleable Commitment and ZeroKnowledge

6:30
 Reception at Massey College 
7:30 
Banquet at Massey College 