Seminars in 2004
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 Vickrey-Groves-Clarke 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 Borsuk-Ulam 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 Rd 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, k-sets and k-levels
  • 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 Fredman-Komlos-Szemeredi scheme
25/5/2004 Pat Morin Bloomier filters
18/5/2004 Jit Bose Level-ancestor queries
11/5/2004 Anil Maheswari The Karger-Klein-Tarjan 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 1-center
  • 2-approximation for diameter
  • 2-approximation for maximum spanning tree
30/3/2004 Yihui Tang Fingerprinting techniques
  • Verifying matrix multiplication
  • Testing equality over a communications link
  • The Karp-Rabin string matching algorithm
23/3/2004 Jason Morrison Markov Chains
  • Definitions
  • Hitting times
  • Cover times
16/3/2004 Pat Morin Three Randomized Algorithms
  • A 2-CNF-SAT 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
  • Average-case analysis of a stable-marriage algorithm
20/1/2004 Pat Morin Chapter 2 - Game Theoretic Techniques
  • An O(n0.71..) time 0-1 game-tree evaluation algorithm
  • Zero-sum game theory
  • Yao's minimax principle
  • A Omega(n0.69) time lower bound
  • Adleman's theorem
13/1/2004 Yihui Tang Chapter 1 - Introduction
  • A randomized min-cut algorithm
  • Las Vegas vs. Monte-Carlo algorithms
  • Analysis of quicksort