Timothy M. Chan
University of Waterloo
Random Sampling
in Computational Geometry


Abstract:
It has been almost fifteen years since the groundbreaking papers by Clarkson
and Shor appeared, popularizing the use of random sampling ideas in solving
geometric problems. These ideas have shaped many of the major developments
in computational geometry over the years. In these lectures, I will give
a gentle introduction to Clarkson and Shor's basic theory, as well as some
of the more recent applications, focusing primarily on samplingbased divideandconquer
methods (as opposed to randomized incremental methods). We will look at
both combinatorial applications of random sampling (e.g., proving kset
and incidence bounds) and algorithmic applications (e.g., finding knearest
neighbors). The emphasis will be on selected examples (chosen for their
simplicity) rather than general formalisms.
Prerequisites:
Basic knowledge about algorithms and randomized algorithms (no problem
after Prabhakar's lectures). Prior knowledge about computational geometry
is not required.

Michele Mosca
University of Waterloo
An Introduction to
Quantum Computation


Abstract:
Information is stored in a physical medium and manipulated by physical
processes. Therefore the capabilities and limitations of any information
processor are determined by the laws of physics. Quantum information and
quantum computation are the natural results of recasting the notions of information
and computation in a quantum mechanical framework. The result is a fundamentally
new way of storing and manipulating information. Quantum communication offers
an exponential reduction in the communication complexity of certain distributed
computation tasks. Quantum computation offers polynomial time factorization
of integers. Quantum cryptography offers intrinsic eavesdropper detection
that leads to some information theoretically secure protocols such as quantum
key expansion. In these lectures I will introduce the basic notions and
notations necessary to appreciate quantum computation. I will focus on the
capabilities and limitations of quantum algorithms. I will also touch briefly
upon quantum error correction, communication complexity and cryptography.
Prerequisites:
An understanding of the basic notions from linear algebra. We will be
working with finite dimensional complex vector spaces. I will not assume
any background knowledge of quantum physics. I will gently introduce Dirac?s
notation. A very basic understanding of group theory will be helpful but
not essential.

Prabhakar Raghavan
Verity Inc. & Stanford University
Randomized Algorithms and
the Probabilistic Method


Abstract:
These lectures will cover the elements of the design and analysis of randomized
algorithms. Students are assumed to have a background in elementary combinatorics,
the analysis of algorithms and basic probability theory. We will cover
a number of probabilistic techniques, together with algorithmic applications
illustrating these techniques. Students will be expected to work on exercises
throughout the series.

Gerhard Woeginger
University of Twente
Approximation Algorithms
and Inapproximability


Abstract:
These lectures will cover things associated with approximation:
algorithms, schemes, inapproximability; most of the illustrating examples
will be from scheduling theory, some from graph theory.
