Sunday May 29
16h45: Departure of the bus from Aix-en-provence TGV

Monday May 30
Morning:
Afternoon:
19h: welcome apéritif
19h30: dinner

Tuesday May 31st
Morning:
Afternoon:
18h-19h: visit of a "truffle field" (read about truffle)

Wednesday June 1st
Morning:
Afternoon: Canoë on the lake

Thursday June 2nd
 Morning:
Afternoon:
Friday June 3rd
Morning:
13h30: Departure of the bus for Aix-en-provence TGV (the bus will be at the station at 3.10 PM).

Quelles ressources (non déterminisme, temps, espace) utilisent les problèmes NP-complets ? Un point de vue de complexité descriptive.

Etienne Grandjean, GREYC Université de Caen

L’un des objectifs premiers de la complexité algorithmique est d’analyser « en quoi » beaucoup de « problèmes naturels » sont intrinsèquement difficiles à résoudre. A cet égard, on remarque que « la plupart »  des problèmes NP-complets combinatoires ont des certificats de taille linéaire et même sont de classe NLIN, c’est-à-dire sont reconnus en temps non déterministe linéaire sur RAMs. (La classe NLIN est une sous-classe stricte de NP.) Un raffinement de la caractérisation, maintenant classique, de la classe NP par la logique Existentielle du Second Ordre (le théorème NP = ESO de Fagin) donne une caractérisation logique de la classe NLIN, d’où l’on déduit certains problèmes naturels NLIN-complets. De façon générale, la complexité descriptive permet de définir les problèmes dans une logique correspondant aux ressources (temps, etc) utilisées par leur calcul.

L’objectif premier de cet exposé est de présenter divers résultats (dont les résultats 1, 2, 3 ci-dessous) qui illustrent en quoi les problèmes NP ou NP-complets naturels utilisent souvent des ressources limitées :
1) Certains problèmes de graphes (exemples : « cycle hamiltonien » et « non planarité ») sont reconnus sur RAMs en temps non déterministe linéaire O(n) en le nombre n de sommets du graphe concerné, donc indépendamment de son nombre d’arêtes.
2) D’autres problèmes (Sac à dos, Clique, beaucoup de restrictions de problèmes NP-complets aux graphes planaires) sont résolubles par RAMs en temps linéaire O(n) et espace sous-linéaire O(sqrt(n)) (et donc en temps déterministe sous-exponentiel 2^(O(sqrt(n)))).
3) Enfin, divers problèmes NP-complets « paramétrés » classiques, typiquement k-Vertex-cover (recouvrement d’un graphe par k sommets), sont résolubles en temps polynomial, et souvent linéaire, en utilisant seulement un nombre limité f(k) de pas non déterministes, c’est-à-dire un nombre dépendant du paramètre k, mais indépendant de la taille de la donnée.
On montrera que les diverses classes de complexité mises en évidence sont, là encore, caractérisables en logique, ce qui leur donne une définition intrinsèque, indépendante du modèle de calcul.

Ces résultats (typiquement 1, 2 et 3) qui établissent que beaucoup de problèmes NP-complets n’utilisent que des ressources limitées me semblent expliquer la difficulté à prouver pour ces problèmes des bornes inférieures de complexité.

On terminera l’exposé en présentant pour quelques problèmes, dont le problème SAT, certaines bornes inférieures de complexité prouvées, pour des modèles de calcul généraux (RAMs). Evidemment, et nous avons cherché à l’expliquer précédemment, ces résultats sont bien loin des bornes inférieures conjecturées pour ces mêmes problèmes.


Hardness versus randomness tradeoffs, or why proving lower bounds = designing deterministic algorithms

Valentine Kabanets, Simon Fraser University, Canada

Theoretical computer science is mostly about upper and lower bounds. When you design an algorithm for some problem A, you show an upper bound on the computational complexity of A. When you show there is no efficient algorithm for A, you prove a lower bound on its complexity.

There are several models of computation where you may want to prove upper and lower bounds. The two models of interest to us will be the uniform model (Turing machines) and the nonuniform model (Boolean or arithmetic circuits). The famous "P versus NP" problem is stated for the uniform model: Are nondeterministic polynomial-time Turing machines more powerful than determistic ones? The problem can also be attacked in the non-uniform model: Can SAT (or any other NP-complete function) be solved by polynomial-size Boolean circuits?

It turns out that proving upper bounds in the uniform model and proving lower bounds in the nonuniform model are intimately related.  For example, in the unlikely event that there is a deterministic polynomial-time algorithm for SAT (and so NP=P), we would also get an exponential lower bound on the size of circuits solving any EXPTIME-complete problem.  In a more likely case that there is a deterministic polynomial-time algorithm for testing if two given arithmetic expressions (say over real numbers) are equivalent, we would also get some nontrivial circuit lower bounds (either for Boolean circuits or arithmetic circuits).

On the other hand, proving that some "explicit" functions require large circuits would also have an implication for algorithms. In particular, proving exponential circuit lower bounds for some EXPTIME-complete function would imply that every probabilistic polynomial-time algorithm can be made deterministic, with only polynomial slowdown. So circuit lower bounds would give us a way to eliminate the use of randomness in a large number of known randomized algorithms (i.e., derandomize them). This direction works for both Boolean and arithmetic problems. Boolean circuit lower bounds imply derandomization of Boolean algorithms, whereas arithmetic lower bounds imply derandomization of the problem of testing if two arithmetic expressions are equivalent.

The apparent equivalence between proving circuit lower bounds and derandomizing probabilistic algorithms will be the main topic of our lectures.



Logical Methods in Combinatorics

Johann Makowsky, Technion, Israel and ETH Zürich
First lecture: Graph polynomials and counting functions.

In the first lecture we introduce several counting functions on graphs, hypergraphs or relational structures. We give a grand tour of theorems which describe some aspects of the behaviour of these counting functions, provided they are subject to some definabilty conditions in some fragment of second order logic. The theorems include Fagin's theorem on the asymptotic probability, the Specker-Blatter theorem on modular counting, various theorems about spectra and linear recurrences for graph polynomials.

Second Lecture: How logic enters?

In the second lecture we discuss the Feferman-Vaught theorem for Monadic Second Order Logic and its pivotal role in proving these theorems. Our main concern here is the separation of the logical (read model theoretic) argument from the purely combinatorial argument.




Complexity Lower Bounds for Randomized and Parallel Computation Trees

Dimitri Grigoriev, CNRS, Rennes, France

Obtaining complexity lower bounds for computation trees is one of the most challenging problems in the complexity theory. There are quite known "topological" methods due to Ben-Or, Bjorner. Lovasz, Yao based on the estimating the Betti numbers. They allow to prove the lower bounds for deterministic computation trees, in particular, the bound n log n for the DISTINCTNESS and SET EQUALITY problems, and the bound n2 for the KNAPSACK and BOUNDED INTEGER PROGRAMMING problems. The "topological" methods fail for recognizing sets with the trivial topological structure, like polyhedra. For obtaining lower bounds for polyhedra we developped differential-geometric methods.

On the other hand all the mentioned methods fail for the randomized computation trees. Therefore, the methods were devised which involve some ideas from algebra, combinatorics, real algebraic geometry, that allowed to prove the lower bounds for randomized computation trees, in particular the bound n2 for the KNAPSACK and BOUNDED INTEGER PROGRAMMING problems and the bound n log n for the DISTINCTNESS problem. For the SET EQUALITY problem and more generally for the BOUNDED SETS DIFFERENCE problem a randomized complexity linear upper bound is known.

Also we show that "parallelism" could speed-up algebraic computations quadratically, and this bound is sharp for the problems of testing arrangements and polyhedra in small-dimensional spaces.

The survey does not suppose any prerequisites.

reference : see publication 76 on http://name.math.univ-rennes1.fr/dimitri.grigoriev/articles.html


Basic algorithms in quantum computation

Frédéric Magniez, CNRS, LRI, Orsay, France

This talk introduces new and complementary contributions of quantum computing in cryptology.
The first part presents quantum cryptographic protocols that have no equivalent in the classical world, whereas the second part explains why the contemporary cryptography would become insecure using a quantum computer (for instance, credit card, numerical signature, encrypted conversation, ...).

More precisely, the first talk presents the quantum protocol of Bennett and Brassard (1984) that allows perfectly secure encrypted communication, whereas no such security exists classically without any assumption. Then, the teleportation protocol of a quantum state by Bennett, Brassard, Crepeau, Jozsa, Peres, and Wootters (1993) is explained.

The second talk shows how to use the fast quantum implementation of Fourier transform for solving combinatorial problems that are known to be hard. In particular, Shor quantum algorithm (1994), which is based on Simon algorithm and allows to factorize any number in polynomial time,  is cast into the general setting of period finding.

Ce cours presentera des contributions complementaires et originales de l'informatique quantique en cryptologie. La premiere partie portera plus particulierement sur l'existence de protocoles cryptographiques sans contrepartie dans le monde classique, alors que la deuxieme expliquera pourquoi les systemes cryptographiques actuels deviendraient vulnerables par l'utilisation d'un ordinateur quantique (par exemple : carte bleue, signatures numeriques, conversation chiffrees...).

Plus precisement, la premiere partie presentera le protocole quantique de Bennett et Brassard (1984) permettant des conversations chiffrees parfaitement sures, alors qu'une telle surete inconditionelle n'existe pas en classique. Puis sera explique le protocole etonnant de teleportation d'un etat quantique de Bennett, Brassard, Crepeau, Jozsa, Peres, et Wootters (1993).

La deuxieme partie montrera comment utiliser l'avantage de l'implementation rapide d'une transformee de Fourier quantique pour resoudre des problemes reputes difficiles. En particulier, l'algorithme quantique de Shor (1994), base sur celui de Simon et permettant de factoriser en temps polynomial, sera presente dans le cadre general de celui de la recherche de periode d'une fonction donnee.

Christophe Dürr, LRI, Orsay, France

In the first part we will introduce the model of quantum circuits and the quantum search algorithm of Lov Grover. It permits to find a good element among N elements with only O(sqrt N) test (of goodness of an element) and it is optimal, while classicaly Omega(N) tests are necessary.

Then in the second part we will see an application of this algorithm to the problem of finding the minimum of a function, and generalize it then to several functions in order to solve the problem of finding a minimum spanning tree.

This cours will be based in an introduction on Grover's algorithm
http://www.lri.fr/~durr/Talks/Marseille02/coursQuantique.ps.gz
and on an article from ICALP'04 on quantum algorithms for graph problems
http://fr.arxiv.org/abs/quant-ph/0401091/


Lower bounds in quantum computation

Sophie Laplante, LRI, Orsay, France
One of the important challenges in quantum computing is to prove lower bounds on the time complexity of computational problems.  The quantum query model, a generalization of decision trees, lends itself well to this task, an has been the most studied.  Two complementary methods have emerged from a long line of research: the polynomial method, and the adversary method.

In the first part of the course, we will introduce the classical, randomized, and quantum query models, present the polynomial and the unweighted adversary methods, and compare the relative strengths of both techniques.

The second part of the course will focus on the quantum adversary method.  We will present two generalizations, the weighted and spectral method. In a recent result of Spalek and Szegedy, it has been shown that these methods are equivalent.  We will see that the techniques are inherently limited, and cannot be used for problems with low certificate complexity.  Finally, we will see that the adversary method can be used to prove lower bounds in classical complexity, in particular, for formula size.

Algorithms for exact linear algebra

Gilles Villard, CNRS, LIP Lyon

We will survey algorithms for the solution of fundamental problems in symbolic and exact linear algebra, with an emphasis on recent and fastest known algorithms.

One may consider that the algebraic complexity of basic linear algebra over an abstract field K is well known. Indeed, if w is the exponent of matrix multiplication over a field K, for instance computing the determinant, the matrix inverse, the rank or the characteristic polynomial of an n x n matrix can be done in softO(nw)= O(nw(log n)c) operations in K (the same holds for the solution of many other problems).

Our objective in this course is to focus on matrices over more concrete domains like K[x] or Z, for which the impact of data size (degree or bit length) on the problem's complexity is much less known. Until recently, it was even considered that an extra factor n was involved, leading to typical costs (based on evaluation/interpolation techniques) in softO(n.nw log|A|) for instance for computing the determinant exactly (log|A| is the degree of the entries over K[x] or the bit length of the entries over Z).

For reducing the algebraic complexity over K[x] or the bit complexity over Z, a main concern is to exploit the interplay of the algebraic structure with the intermediate expression swell. Several authors have successfully addressed the question during the last years. This research surprisingly shows that certain symbolic problems on dense matrices can actually be solved in about the same number of operations as for the corresponding matrix multiplication.

Especially around system solution, the determinant, the matrix inverse, and matrix normal forms, we will present techniques for obtaining fast deterministic and randomized algorithms leading to partial answers for the following two questions. If MM(n,d) is the cost for multiplying two n x n polynomial matrices of degree d over K, which problems can be solved in softO(MM(n,d)) operations in K? If MM(n,log|A|) is the cost for multiplying two n x n integer matrices, which problems can be solved in softO(MM(n,log|A|)) bit operations?


Recent advances in the Blum-Shub-Smale model

Peter Bürgisser, Paderborn

The BSS-model is a natural mathematical extension of the usual Turing model of computation. A main motivation for its introduction was to provide a theoretical foundation for numerical computation with real numbers in the sense of theoretical computer science. That is, by defining complexity classes, studying reductions etc.

The restriction of the BSS-model obtained by disallowing multiplications (additive model) is now quite well understood: we know of a large variety of complete problems and understand the connection of the additive model to the standard discrete model.

For the general BSS-model, the situation is considerably more complicated and the state of art is less satisfactory. Recently, the introduction of counting complexity classes for the BSS-model has led to some advances. For the computation of some natural invariants of (semi)algebraic sets in turned out to be possible to obtain a classification in terms of completeness results. The invariants studied so far are the (topological) Euler characteristic, Betti numbers and the Hilbert polynomial. These results can be interpreted both in the Turing and BSS-model of computation. and give rise to several new and exciting open problems.

The purpose of the lectures is to give an overview of these results and the underlying ideas, starting with the  basic definitions.


Valiant's model

Guillaume Malod, Kyoto University

The topic of this course is the algebraic complexity classes introduced by Valiant: much as P can be seen as the class "feasible" boolean decision problems in the possibly larger class NP, VP gathers the "reasonably computable" polynomial families in the possibly larger class VNP. As the word "possibly" in the previous sentence indicates, the exact relationship between the classes of easy and difficult problems is open in both settings.

The main result of Valiant's theory is the completeness of the permanent family of polynomials for the class VNP, a completeness result which is a nice parallel to its completeness for the counting class #P, and which highlights the  intractability of this problem. This theory can also be viewed as a background for symbolic manipulations of polynomials, explaining the difficulty of certain problems and the computaional consequences of the different ways of representing polynomials.

The first part of the course will focus on the basic definitions and properties, which will be illustrated by proving the completeness of the permanent and studying the complexity of the determinant. The second part of the course will give additional results and present possible variations of the theory.
Lower Bounds in Algebraic Complexity by Algebraic Geometry

Kenneth Regan (Buffalo, USA)

The first half will survey Volker Strassen's "Degree Method", which when coupled with the Baur-Strassen "Derivative Lemma", produces Omega(n\log n) lower bounds on the algebraic circuit size of many natural families of low-degree polynomials.  For 33 years and counting, these are the best general lower bounds known!  However, the basic method does not distinguish any complexity features of functions believed to be truly hard, from those of simple polynomials such as f(x_1,...,x_n) = x_1^n + ... + x_n^n, for which n\log_2(n) is tight. Indeed, the application of Bezout's inequality in Strassen's proof, to the mapping-Jacobian variety J(f) of f in Cartesian coordinates, by itself limits the method from proving any higher lower bounds.

The second half will survey several speculative attempts, by Mulmuley-Sohoni, myself, and others, to rise above this limitation.  We explain how the Cartesian vision often misses the infrared algebraic structure. For the simplest example, x=0, x2=0, and x3=0 are the same equation to Descartes, but not to Grothendieck!  The various attempts can be classed as:

(1) Apply Strassen's method to entities I(f) that give richer structure than
    J(f), under restricted conditions studied by Raz, Shpilka-Wigderson, and
    others.
(2) Extend Strassen's method by adapting the notion of "degree" to higher
    geometry.  Some ignominious but interesting failures...
(3) Replace "degree" by deeper complexity notions, such as Mulmuley-Sohoni's
    "partial-" adaptation of Mumford's seminal study of "stability".

The talk will emphasize conceptual pictures, to encourage others to brave the considerable technical machinery of at least one of these approaches. (It is possible that a new result will throw the focus on just one of them.)
Tellegen's principle and the synthesis of algorithms

Erich Kaltofen (North Carolina State University, USA)

Tellegen's principle from circuit theory states that a linear arithmetic circuit for computing a matrix times vector product can be reversed to obtain the transpose matrix times vector product. The principle is a special case of the reverse mode in automatic differentiation. Algorithms for transposed matrices are thus synthesized. Those algorithms have the same algebraic time complexity. The space complexity can be preserved as well in certain models of computation via results from automatic differentiation (pointed out to me by Eric Schost).

Recently, these transformations have been employed to design fast algorithms: weighted power sums, determining the minimum polynomial of an algebraic number via power projections, bilinear projections of matrix powers, solution of transposed Vandermonde systems, etc.

Fast computer implementations of algorithms derived by this abstract technique are in use today. The talk will cover the proof of the principle, complexity theoretic considerations, and several applications.
Quantum communication complexity

Harry Buhrman (CWI, Netherlands)

We will review the area of quantum communication complexity. Although a central theorem of Holevo shows that one qubit can not be used to carry more than one classical bit of information, we show that in certain distributed tasks qubits can be used to reduce the communication. We will show how this has implications back to physics and can be used to construct experiments that are more robust to noise than what was previously known.