Date 
Speaker 
Topics 
21/12/2004 
Anil Maheshwari 
Clearing markets optimally II

14/12/2004 
Anil Maheshwari 
Clearing markets optimally

7/12/2004 

Open problem and planning session

30/11/2004 
Michiel Smid 
The gap property

23/11/2004 
Pat Morin 
Mechanisms for task assignment

16/11/2004 
Pat Morin 
VickreyGrovesClarke mechanisms

9/11/2004 
Evangelos Kranakis 
Composition of hash functions II

2/11/2004 
Evangelos Kranakis 
Composition of hash functions

26/10/2004 
Jit Bose 
Sperner's Lemma and Tucker's Lemma

19/10/2004 
Jit Bose 
The BorsukUlam Theorem and its proof

12/10/2004 
Leszek Gasienic 
M2M multicast in packet radio networks

5/10/2004 
Costis Georgiou 
Unfairness in online scheduling

28/9/2004 
Hua Guo 
All pairs shortest paths

21/9/2004 
Hua Guo 
Shortest paths  A survey

14/9/2004 
Esther Moet 
On witnesses wrt to guarding polygons

7/9/2004 
Michiel Smid 
Covering R^{d} with cones
 A decomposition of the hypercube
 Kuhn's triangulation of the hypercube

31/8/2004 
Yihui Tang 
Sorting and selection with limited space
 Upper and lower bounds for sorting
 Upper and lower bounds for selection

24/8/2004 
Partha P. Goswami 
Finding the k nearest neighbours to a query segment

17/8/2004 
Stefan Langerman 
Retroactive data structures

3/8/2004 
Pat Morin 
Crossing numbers and Erdös problems

13/7/2004 
Jason Morrison 
Centroid decomposition II

6/7/2004 
Jason Morrison 
Centroid decomposition I

29/6/2004 
?? 
??

22/6/2004 
Anil Maheshwari 
Perfect matching algorithms

15/6/2004 
Harish Gopala 
Zonoid depth
 Zonoids, ksets and klevels
 Computing one or all zonoids
 Depth computation (decision version)
 Depth computation (optimization version)

8/6/2004 
Michiel Smid 
Perfect hashing II
 Dynamization of FKS (Dietzfelbinger et al.)

1/6/2004 
Michiel Smid 
Perfect hashing I
 Universal hashing
 The FredmanKomlosSzemeredi scheme

25/5/2004 
Pat Morin 
Bloomier filters

18/5/2004 
Jit Bose 
Levelancestor queries

11/5/2004 
Anil Maheswari 
The KargerKleinTarjan O(n+m) MST algorithm

4/5/2004 
 
Open problem session

27/4/2004 
Yihui Tang 
Bloom filters II: Applications

20/4/2004 
Yihui Tang 
Bloom filters I: The data structure and its analysis

13/4/2004 
Jit Bose 
Sublinear algorithms for metric spaces II

6/4/2004 
Jit Bose 
Sublinear algorithms for metric spaces I
 (1+eps)approximation for the 1center
 2approximation for diameter
 2approximation for maximum spanning tree

30/3/2004 
Yihui Tang 
Fingerprinting techniques
 Verifying matrix multiplication
 Testing equality over a communications link
 The KarpRabin string matching algorithm

23/3/2004 
Jason Morrison 
Markov Chains
 Definitions
 Hitting times
 Cover times

16/3/2004 
Pat Morin 
Three Randomized Algorithms
 A 2CNFSAT algorithm
 Estimating the number of satisfying assignments for DNF formulas
 Finding witnesses for boolean matrix multiplication

9/3/2004 
Yihui Tang 
Martingales
 Conditional expectation
 Martingale sequences
 The Martingale stopping theorem

2/3/2004 
David Wood 
The (Lovasz) Local Lemma
 The Local Lemma
 Chromatic number as a function of maximum degree
 Star colorings

24/2/2004 
Anil Maheshwari and Yihui Tang 
Two applications of Chernoff's bounds
 Routing in a parallel computer
 A wiring problem

17/2/2004 
Yihui Tang 
Tail Estimates
 Markov's inequality
 Chebyshev's inequality
 Chernoff's bounds

10/2/2004 
?? 
??

27/1/2004 
Evangelos Kranakis 
Chapter 3  Moments and Deviations
 The coupon collector's problem
 Averagecase analysis of a stablemarriage algorithm

20/1/2004 
Pat Morin 
Chapter 2  Game Theoretic Techniques
 An O(n^{0.71..}) time 01 gametree evaluation algorithm
 Zerosum game theory
 Yao's minimax principle
 A Omega(n^{0.69}) time lower bound
 Adleman's theorem

13/1/2004 
Yihui Tang 
Chapter 1  Introduction
 A randomized mincut algorithm
 Las Vegas vs. MonteCarlo algorithms
 Analysis of quicksort
