33ème École de printemps d'informatique
théorique
33rd Theoretical Computer
Science Spring School
May 30 - June 3, 2005
Complexité algorithmique
Computational Complexity
Montagnac-les-truffes, Alpes de Haute Provence
Program:
L´essentiel du temps sera
consacré à des cours organisés pour amener les
participants
de l´introduction à un sujet jusqu´aux
résultats les plus récents. Nous envisageons de laisser
aussi dans le programme une (petite) place à des exposés
proposés par les participants eux-mêmes.
Most of the time will
be devoted
to invited talks. If time allows there might also be a few contributed
presentations.
The official languages of the school are English and French. We expect
that most of the talks will be in English.
- Peter
Bürgisser (Paderborn, Germany)Recent
advances in the Blum-Shub-Smale problem
abstract, slides.pdf,
picture.jpg
- Harry Buhrman
(CWI, Netherlands): quantum communication
complexity abstract,
slides.pdf, picture.jpg
- Christoph
Dürr (Orsay) basic
algorithms in quantum computation,
abstract, slidesD.pdf, picture.jpg
- Etienne
Grandjean (Caen, France)Quelles
ressources (non déterminisme, temps,
espace) utilisent les problèmes NP-complets ? Un point de
vue de complexité descriptive,
abstract, slides.pdf, picture.jpg
- Dimitri
Grigoriev (CNRS, Rennes, France):
Complexity Lower Bounds for Randomized and Parallel Computation Trees,
abstract,
slides.pdf, picture.jpg
- Valentine Kabanets
(Simon Fraser University, Canada): Hardness
versus randomness tradeoffs, or why proving lower bounds = designing
deterministic algorithms,
abstract, slides1.ppt,
slides2.ppt, picture.jpg
- Erich Kaltofen Tellegen's
principle and the synthesis of algorithms abstract,
slides1.pdf, slides2.pdf, picture.jpg
- Sophie
Laplante (Orsay): lower
bounds in quantum computation,
abstract , slides.pdf,
picture.jpg
- Frédéric
Magniez (CNRS, Orsay): basic
algorithms in quantum computation,
abstract, slides.pdf, picture.jpg
- Janos Makowsky
(Technion, Israel and ETH Zürich): Logical
Methods in Combinatorics,
abstract, slides.pdf, picture.jpg
- Guillaume Malod (Kyoto University ): Valiant's
model,
abstract, slides.pdf, picture.jpg
- Kenneth Regan
(Buffalo,
USA): lower bounds in algebraic complexity by
algebraic geometry,
abstract, slides.pdf, picture.jpg
- Gilles Villard
(CNRS, Lyon): Algorithms for exact linear
algebra,
abstract, slides.pdf, picture.jpg
Contributed talks:
- Simon
Perdrix,
Graph states, slides.pdf, picture.jpg
- Vincent Nesme, slides.pdf, picture.jpg
- Christine
Gassner,
Structures with P=NP with respect to the uniform model of computation, slides.pdf, picture.jpg
- Kenneth Regan,
Open problems, slides.pdf, picture.jpg
Click here for schedule.
Comité scientifique et d'organisation - Scientific
and organisation committee:
Pascal Koiran
Frédéric Magniez
Natacha Portier
Comité
de pilotage - Steering committee:
Roberto Amadio (LIF,
Marseille)
Pierre-Louis Curien
(PPS, Paris),
Daniel Krob (LIX,
Palaiseau)
Jean-Michel
Muller (LIP, Lyon)
Jean-Eric Pin (LIAFA).
Objectifs
(Goals)
Accès Directions
Montagnac-les-truffes, ou Montagnac-Montpezat, est un petit
village des
alpes de haute provence. L'école aura lieu dans son VVF
Montagnac-the-truffles
is a small
village in central Provence, very close to the Verdon Canyon. The
school will be held in a VVF
holiday resort.
Si vous venez du sud-est de la France, nous vous conseillons de venir
en voiture.
If you come from south-east France, driving
should be most convenient.
Dimanche 29 mai vers 16h45, un bus réservé par nos soins
quittera la gare d'Aix-en-provence-TGV le dimanche après-midi
pour arriver environ 2h plus tard sur le lieu de l'école, et
vous ramènera à la gare (arrivée prévue
vers 15h10) le vendredi après le
repas. Le bus se trouvera sur le parking des bus, vous pouvez regarder ici à quoi il ressemble.
On Sunday May 29th at 4.45 PM, a bus will take
you from Aix-en-Provence-TGV train
station to the school location (it is a 2 hour ride). The bus will be
waiting on the "parking des bus" (P bus), here is a picture of it.
The bus will also take you back to the station on Friday after
lunch (the bus will be at the station at 3.10 PM).
Si vous arrivez à partir de lundi à la gare de Marseille
Saint-Charles : vous pouvez prendre le bus jusqu'à Riez (2h de
trajet, voir les
horaires) puis nous contacter ou prendre un taxi (environ 10
km jusqu'à Montagnac). Location de voiture à Riez ?
à Gréoux ?
If your train takes you to Marseille
(Saint-Charles station) : a bus can take you to Riez (2h ride, no bus
on week ends) and then take a taxi to Montagnac (10 km). Bus
schedule.
Si vous arrivez à l'aéroport de Marseille-Marignane,
prenez la navette jusqu'à la gare Saint-Charles puis
reportez-vous au paragraphe précédent.
If you land at Marseille-Marignane airport take a
shuttle to Saint-Charles station and then take a bus as explained above
(not recommended!)
Sortie
Social
Program
Mercredi, l'après-midi est libre. Vous pouvez profiter
de la
piscine chauffée, aller vous promener, visiter le musée de la
préhistoire à Quinson... Mais si ce pays est beau,
c'est grace au Verdon.
Au dessous du VVF se trouve un de ses lacs. C'est pourquoi nous vous
proposons une sortie en kayak
sur le lac. Ce sont des canoë de lac pour deux ou trois personnes,
qui ne demandent pas de condition physique particulière ni de se
mouiller. La sortie dure environ 2h30 : aller-retour au barrage (voir
le plan) et visite en kayak du
site préhistorique des grottes de l'église à Baudinard. Sur
chaque kayak, un bidon est prévu pour mettre les papiers et les
appareils photos. N'hésitez pas, c'est magnifique ! Vous avez
juste besoin d'une tenue confortable.
prix par personne : environ 16 euros (à payer sur place)
Wednesday afternoon is free. You can enjoy the
heated swimming pool, go hiking, visit the museum of prehistory in
Quinson... But this country is beautiful thanks to the Verdon
river ("Verdon" because the water is green). One of the lake is just
behind the conference location. That is the reason why we propose a ride with a canoe on the
lake. These
canoe are large and stable, for two or three people, and you will not
need
to get wet. The trip is two hours and a half long: go to the barrage
and
back (look at the map) and visit
the
prehistoric grot
of the church in Baudinard.
On every canoe is a waterproof box for papers and camera. You will not
regret this wonderful excursion! You just need comfortable clothes.
Price: approximately 16 euros (to be paid at the conference)
A Few Links
plan
michelin (map)
petite présentation du village de Montagnac
tout sur
la
truffe de Montagnac
page d'inconnus sur le
village
des
liens sur la région
le
VVF de Montagnac-Montpezat
le
Verdon
Some previous spring schools:
26e École de printemps d'informatique
théorique
Algèbres Max-Plus et applications en informatique
et automatique.
http://www.inria.fr/actualites/colloques/1998/MAXPLUS98Acces-fra.html
27e École de printemps d'informatique théorique
Codage et Cryptographie 1999
http://www-rocq.inria.fr/codes/Anne.Canteaut/ECOLE/
28e École de printemps d'informatique théorique
Euro Summer School
Pavages 2000
http://www.inria.fr/actualites/colloques/2000/PAVAGES00-fra.html
29e Ecole de printemps d'informatique théorique
Arithmétique des ordinateurs
http://www.inria.fr/actualites/colloques/ado/
30ème Ecole de printemps d'informatique théorique
SEMANTIQUE DES LANGAGES DE PROGRAMMATION
http://www.pps.jussieu.fr/~ecole/
31ème Ecole de printemps d'informatique théorique
Algorithmique distribuée
http://www.liafa.jussieu.fr/ecole-de-printemps/
32ème Ecole de printemps d'informatique théorique
Concurrency theory and applications - April 26-30, 2004
http://www.cmi.univ-mrs.fr/epit32/
Inscription Registration
The deadline was april 22nd, 2005. You can still send your
registration
form, maybe there is some place left!
fichier texte à
récupérer et à envoyer par mel ou par la poste
text file to be received by mail
L'école peut avoir lieu grâce
au
soutien
financier des organismes suivants:
Nous les en remercions.
Please consult this page from
time to
time as it will be regularly updated.
last update: july, 2005
