Program

Timothy M. Chan

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 sampling-based divide-and-conquer methods (as opposed to randomized incremental methods). We will look at both combinatorial applications of random sampling (e.g., proving k-set and incidence bounds) and algorithmic applications (e.g., finding k-nearest 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

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

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

Approximation Algorithms
and Inapproximability

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