MPII Home Page MPII Home Page MPII Home Page
ALCOM-FT Home Page
Other Conferences Homepage ADFOCS 2002



Homepage
Program
Registration
Accomodation
Grants
Feedback




         



Program

The lectures are scheduled in twelve blocks of about 1 1/2 hours each. Eight of the lecture blocks will be followed by another 1 1/2 hours of exercises/discussion . During the exercise periods, the respective lecturer will be around, as well as some snacks and drinks.

Wednesday, there will be lectures and tutorials in the morning. In the afternoon, there will be an excursion to the old iron and steel works of Völklingen, declared World Cultural Heritage by the UNESCO in 1994; the bus leaves at 14.30 in front of the institute.


Schedule



September 9
Monday
September 10
Tuesday
September 11
Wednesday
September 12
Thursday
September 13
Friday
8.30-9.00
Registration/Welcome




9.00-12.30 Raghavan
Lecture+Tutorial
Woeginger
Lecture+Tutorial
Chan
Lecture+Tutorial
Mosca
Lecture+Tutorial
Chan
Lecture

Mosca
Lecture

12.30-13.30 Lunch
break
Lunch
break
Lunch
break
Lunch
break
Lunch
break
13.30-18.30 Woeginger
Lecture+Tutorial

Raghavan
Lecture
Raghavan
Lecture+Tutorial

Woeginger
Lecture
Excursion Chan
Lecture+Tutorial
Mosca
Tutorial+Lecture
Evening
Dinner






Lecture(r)s

Below you find short abstracts of the lectures together with an indication of useful prerequisites. Clicking on the photos gets you to the respective lecturers' homepage.

Timothy M. Chan

University of Waterloo

Random Sampling
in Computational Geometry

to Timothy Chan's homepage

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

University of Waterloo

An Introduction to
Quantum Computation

to Michele Mosca's homepage

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

to Prabhakar Raghavan's homepage

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

to Gerhard Woeginger's homepage

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.


Organization

Concept and web pages borrowed from last year´s ADFOCS, local organization by Piotr Krysta and Stefan Funke, Petra Mayer, Gabi Holzer and Roxane Wetzel . For comments or questions send an email to adfocs@mpi-sb.mpg.de . Partially supported by the Information Society Technologies Programme of the EU under contract number IST-1999-14186 (project ALCOM-FT ).


ADFOCS 2002 organized by Piotr Krysta & Stefan Funke ; WWW page last updated on Wednesday, 29 May 2002.