Probabilistic verification - Michel de Rougemont (12 h)
Online algorithms - Adi Rosen (12 h)
Langues du cours :
Première partie (probabilistic verification) en Français, si tout le monde comprend le Français, sinon en Anglais. Deuxième partie (online algorithms) en Anglais.
Supports :
Le cours se fait au tableau et des notes de cours sont disponibles sur le serveur pour une partie des cours. Un lien pointe vers une version .pdf de la 1ère partie. Des exercices sont données au fil du cours.
Objectives
Approximation algorithms and online algorithms are two algorithmic paradigms which deal with two kinds of difficulties that arise in computing exact solutions that arise in computation.
On the one hand, today, most applied optimization problems suffer from the fact that finding exact solutions to them is NP-hard and if one wants to be computationally feasible, one has to settle for finding approximate solutions to these problems. This is the content of approximation algorithms: to understand the approximability of NP-hard problems. Probabilistic verifications (IP, PCP, property testing) are important tools closely related to questions of approximability. For instance, these models
separate between problems which cannot be approximated, from those, including NP-complete problems, which are approximable in constant time.
On the other hand, several computationally "easy" problems become hard when the input is revealed piece by piece, and the algorithms have to take an irrevesible action upon receipt of each piece. This is often the case in several "data intensive" problems that arise in practice. Here again, one has to settle for computing approximate solutions, and the study of problems in this model constitutes the area of online algorithms.
This course is aimed at giving an introduction to probabilistic verification and to online algorithms.
Probabilistic verification
The first part of the course concerns the probabilistic verification models: IP, PCP and Property Testing.
Interactive proofs (IP) generalize the class NP for verification problems to the setting where the verifier is probabilistic (as BPP generalizes P for classical decision problems).
In the PCP model, the verifier is restricted to be in BPP and to access the i-th bit of a long proof in constant time. In Property Testing, the Tester
has a similar access to a given input, and must approximately decide a property.
These models have strong connections with Approximation algorithms, as they separate between problems which can't be approximated from those, including NP-complete problems, which are approximable in constant time.
There will be one Homework assignment, on this part, given in lecture 2. It has be returned in lecture 4.
Homeworks will count between 10% and 20% of the global grade. Useful reference for HW 1.
Online algorithms
The area of online algorithms has become an established field in theoretical computer science. It deals with the design and analysis of algorithms that operate in a state of incomplete information. Typically, an online algorithm receives its input piece by piece, and must take an irreversible action upon the receipt of each piece of input without knowledge of future input. Such scenarios are predominant and occur, e.g., in the management of (limited space) cache, in admission and routing in communication networks, in scheduling, etc.
When no prediction of the pattern of the input sequence is available, an accepted method to analyze the performance of online algorithms is "competitive analysis". In competitive analysis one compares the performance (e.g., overall system cost) of an online algorithm, to the performance of an utopian, clairvoyant, algorithm, that knows the entire input in advance. This type of analysis allows one to obtain robust results that do not depend on specific input patterns.
In this course we will try to present the basic concepts of online algorithms and competitive analysis, to cover a number of "classical" results (e.g., k-server problems, metrical task systems), as well as some recent research directions and open problems.
Contenu du cours
The topics discussed will come from the following list (subject to some changes; probably not all topics will be covered).
Probabilistic Verification: IP and MIP, Protocol for the permanent and QBF, IP=PSPACE, See the class notes (chapter 2).
PCP model, Holographic proofs. NP= PCP(n^3, 1), see the class notes (chapter 2),
Arora-Barak,2009,chapter 11,, Non approximability of Maxclique and Maxsat, see the class notes (chapter 3),
