SCIENTIFIC PROGRAMS AND ACTIVITIES

April 19, 2014

A workshop in honour of Allan Borodin's 60th birthday
June 22 - 23, 2001

Friday June 22
9:00-9:30 Registration and Breakfast
9:30-10:00 Ian Munro, University of Waterloo
A Worst Case Constant Time Priority Queue
10:05-10:35 Jeff Edmonds, York University
TCP has Competitive Flow Times
10:40-11:10 Jon Kleinberg, Cornell University
Small-World Phenomena and the Dynamics of Information
11:15-11:45 Steven Rudich, Carnegie Mellon University
Formal Code Obfuscation
11:50-12:05 TBA
12:10-2:00 Lunch
2:00-2:30 Martin Tompa, University of Washington
Identifying Motifs in Orthologous DNA Sequences from Multiple Species
2:35-3:05 David Kirkpatrick, University of British Columbia
Restructuring Ordered Binary Trees
3:10-3:40 Madhu Sudan, Massachusetts Institute of Technology
Random walks with "Back Buttons"
3:45-4:15 Coffee Break
4:15-4:35 C. C. Gotlieb, University of Toronto
"The New Real Estate" (Control of channels)
4:40-5:10 Panayiotis Tsaparas, University of Toronto
Link Analysis Ranking Algorithms on the World Wide Web
5:15-5:45 Adi Rosen, Technion
Tight Bounds on the Performance of Longest-In-System on DAGs
   
Saturday June 23
9:00-9:30 A. A. Razborov, Steklov Mathematics Institute/IAS
Proof Complexity of Pigeonhole Principles
9:35-10:05 Leslie Valiant, Harvard University
Quantum Computations that Can be Simulated Classically in Polynomial Time
10:05-10:35 Coffee Break
10:35-11:05 Nicholas Pippenger, University of Bristish Columbia
Random Boolean Functions
11:10-11:40 Shai Ben-David, Technion
Computational Complexity vs. Statistical Generalization in Learning -- A survey of current knowledge and major questions
11:45-12:15 Hisao Tamaki, Meiji University
Heuristic algorithms for Euclidean TSP based on Arora's dynamic programming scheme
12:15-2:00 Lunch
2:00-2:30 Avi Wigderson, Institute for Advanced Study
Expanders - where Combinatorics and Algebra compete and cooperate
2:35-3:05 Eli Upfal, Brown University
Can Entropy Characterize Performance of Online Algorithms?
3:10-3:40 Baruch Schieber, IBM - T.J. Watson Research Center
Online Server Allocation in a Server Farm via Benefit Task System
3:40-4:10

Coffee Break

4:10-4:40 Ran El-Yaniv, Technion
On online learning of expert advice
4:45-5:15 Yuval Rabani, Technion
Geometric Search Structures in High Dimensional Spaces
5:20-5:50 Rafail Ostrovsky, Telcordia Technologies
Non-Interactive and Non-Malleable Commitment and Zero-Knowledge
6:30
Reception at Massey College
7:30 Banquet at Massey College