Composition de l'équipe
  Responsable
    SANTHA Miklos

  Membres permanents
    ALLOUCHE Jean-Paul
    DE ROUGEMONT Michel
    FIORENZI Francesca
    GOUYOU-BEAUCHAMPS Dominique
    KERENIDIS Iordanis
    LAPLANTE Sophie
    MAGNIEZ Frédéric
    MANOUSSAKIS Yannis
    OCHEM Pascal
    ROSEN Adi
    SANTHA Miklos

  Membres non-permanents
    BOROZAN Valentin
    CHAILLOUX André
    JOSUAT-VERGES Matthieu
    KONRAD Christian
    MAGNIN Loïck
    MENDY Gervais
    MONTERO LEANDRO Pedro
    NGUYEN Quoc Thinh
    TRACOL Mathieu
    XIAO David
    ZEITOUN Xavier

  Visiteurs
    AGUEDA Raquel
    LASSAIGNE Richard
    SIKORA Jamie

  Stagiaires
    RENAULT Marc

Thèmes de recherche
  Vérification
  Model-Checking
  Algorithmique
  Algorithmes probabilistes
  Combinatoire
  Calcul quantique
  Algorithmes approchés
  Complexité
  Combinatoire des mots
  Combinatoire énumerative
  Algorithmes en ligne
  Théorie de la cryptographie
  Algorithmique de graphes

Contrats en cours
  ALGOQP
  QAP
  VERAP
  GT CMF
  QCCC
  HSP
  QRAC
  CSQIP
  Cryptanalyse Quantique
  GAP
  GT IQ
  ICOMB
  JST-ICT
  MASA
  Réseaux quantiques
  RESQ
  VERA
  CRYQ

Collaborations
  GDR ICQ
  Ã‰quipe de Logique Mathématique Université Paris Diderot Paris 7
  Partitions d'entiers à l'interface de la combinatoire, des q-series et de la théorie des nombres
  Génération Aléatoire: Modèles, Méthodes, Algorithmes
  Quantum algorithms and complexity theory

Thèses et habilitabions récentes
  Ã‰numération de tableaux et de chemins, moments de polynômes orthogonaux
  " Méthodes combinatoires et algébriques en complexité de la communication."
  Algorithme quantiques dans les groupes nilpotents

TBA
Ben Rossman
Jeu 27 mai 2010 - 14h00

Scheduling strategies for efficient interruptible algorithms
Spyros Angelopoulos
Mar 09 mars 2010 - 11h00

Evasiveness and the Music of Primes
Raghav Kulkarni
Mer 03 mars 2010 - 14h00

On the performance of approximate equilibria in congestion games
Giorgos Christodoulou
Ven 12 février 2010 - 11h00

Universal Cycles, 2-Radius Sequences, and Fetching Huge Objects into Small Memory
Yeow Meng CHEE
Jeu 04 février 2010 - 14h30

Destructive rule-based properties and first-order logic
David Duris
Jeu 04 février 2010 - 13h30

Near-optimal extractors against quantum storage
Thomas Vidick
Jeu 14 janvier 2010 - 14h00

An Efficient Algorithm for Replicating Data in Modern Networks
Mauro Sozio
Mar 24 novembre 2009 - 14h00

Classical and Quantum Fanouts have the same Power
Simon Perdrix
Jeu 12 novembre 2009 - 14h00

Information Flow in Secret Sharing Protocols
Damian Markham
Jeu 05 novembre 2009 - 14h00

Tight bound for Gap Hamming Distance
Oded Regev
Jeu 15 octobre 2009 - 14h00

Using Merlin to Estimate Histograms and Recursively Find Collisions, with Applications
David Xiao
Jeu 01 octobre 2009 - 14h00

SZK Proofs for Black Box Group Problems
Bireswar Das
Jeu 17 septembre 2009 - 14h00

On quantum mechanics over the reals
Matthew McKague
Mar 15 septembre 2009 - 11h30

Network Games with Quantum Strategies
Giannicola Scarpa
Lun 07 septembre 2009 - 11h30

Two-message quantum interactive proofs are in PSPACE.
Rahul Jain
Jeu 09 juillet 2009 - 14h00

Correlation Clustering with Noisy Input.
Claire Mathieu
Jeu 09 juillet 2009 - 11h30

Approximate Clustering without the Approximation Algorithm
Anupam Gupta
Jeu 25 juin 2009 - 10h00

An introduction to "continuous variable" quantum information
Barry Sanders
Mar 23 juin 2009 - 15h30

The Quantum Prisoners Multilemma, and other quantum games.
McGettrick, Michael
Ven 19 juin 2009 - 11h30

Online Scheduling of Bounded Length Jobs to Maximize Throughput
Christoph Durr
Jeu 11 juin 2009 - 11h30

Des piles de sable aux automates de sable
Benoît Masson
Jeu 07 mai 2009 - 14h30

Hidden Polynomial Function Graphs
THOMAS DECKER
Jeu 07 mai 2009 - 11h30

Couplages parfaits dans les graphes cubiques
Louis Esperet
Jeu 30 avril 2009 - 14h00

Algorithme d'approximation pour l'ordonnancement on-line de tâches avec pénalités
Nicolas Thibault
Ven 10 avril 2009 - 11h30

TBA
Marion Le Gonidec
Jeu 09 avril 2009 - 14h00

Analyse statistique pour Markov Decision Processes et Automates Probabilistes
Mathieu Tracol
Jeu 09 avril 2009 - 11h30

Autour des surpartitions et des identités de type Rogers-Ramanujan
Olivier Mallet
Jeu 02 avril 2009 - 11h30

On the Black-box Complexity of PAC Learning
Daviv Xiao
Mar 10 mars 2009 - 11h30

Unique Games with Entangled Provers are Easy
Oded Regev
Jeu 26 février 2009 - 11h30

Efficient Isomorphism Testing for a Class of Group Extensions
Francois le Gall
Ven 20 février 2009 - 14h00

The Compressible Web: An Ounce of Knowledge for a Ton of Data?
Alessandro Panconesi
Ven 30 janvier 2009 - 11h30

Approximation Algorithms on Bounded Dimensional Metric Spaces
Hubert Chan
Jeu 18 décembre 2008 - 11h30

Rounding Parallel Repetitions of Unique Games
David Steurer
Jeu 11 décembre 2008 - 11h30

On unconditional deterministic polynomial factorization over finite fields
Gabor Ivanyos
Mar 09 décembre 2008 - 11h30

Total positivity, matroids, and polytopes
Alex Postnikov
Jeu 27 novembre 2008 - 11h30

Information Theoretic Approaches to Whole Genome Phylogenies
Benny Chor
Jeu 13 novembre 2008 - 11h30

Property Testing in the Underlying Graph Model
Oded Lachish
Jeu 06 novembre 2008 - 11h30

Finding optimal flow efficiently
Simon Perdrix
Jeu 30 octobre 2008 - 11h30

On the hitting times of quantum versus random walks
Peter Richter
Jeu 16 octobre 2008 - 11h30

Random algorithms for recognizing black-box groups
Peter P. Palfy
Jeu 02 octobre 2008 - 11h30

Expander Flows, Graph Spectra and Graph Separators
Umesh Vazirani
Mar 01 juillet 2008 - 15h00

Sampling-Based Algorithms for Dimension Reduction
Amit Deshpande
Mar 01 juillet 2008 - 11h30

Making Classical Zero Knowledge Protocols Secure Against Quantum Attacks
Pranab Sen
Jeu 26 juin 2008 - 11h30

Molecular algorithms: combining efficiency with robustness
Ashish Goel
Ven 20 juin 2008 - 11h30

Lower Bounds for Satisfiability and Related Problems (Part II)
Dieter van Melkebeek
Jeu 12 juin 2008 - 11h30

Lower Bounds for Satisfiability and Related Problems
Dieter van Melkebeek
Jeu 05 juin 2008 - 14h00

Disjointness is hard in the multi-party number-on-the-forehead model
Troy Lee
Mar 20 mai 2008 - 14h00

Mechanism design for scheduling unrelated machines
Elias Koutsoupias
Lun 19 mai 2008 - 11h30

Loss-tolerant quantum coin flipping
Gilles Brassard
Ven 09 mai 2008 - 14h30

Quantum Cellular Automata
Vincent Nesme
Mar 29 avril 2008 - 11h30

A strongly polynomial algorithm for finding optimal policies for one dimensional Markov decision processes
Guy Even
Jeu 17 avril 2008 - 11h30

Cuts, Embeddings and Flows
Nisheeth Vishnoi
Jeu 10 avril 2008 - 11h30

Mixing on Random Graphs
Allan Sly
Jeu 03 avril 2008 - 11h30

Hierarchical Graph Decompositions for Minimizing Congestion
Harald Raecke
Jeu 20 mars 2008 - 11h30

Design and Analysis of Classic and Quantum Network Coding
Kazuo Iwama
Lun 25 février 2008 - 16h30

PSPACE has one round quantum multiprover interactive proofs
Keiji Matsumoto
Lun 25 février 2008 - 15h05

Entanglement and Multi-Prover Interactive Proof Systems
Hirotada Kobayashi
Lun 25 février 2008 - 14h00

Underapproximation for Model-Checking Based on Universal Circuits
Arie Matsliah
Lun 18 février 2008 - 11h00

On divergence Information (Lecture 2)
Ashwin Nayak
Jeu 14 février 2008 - 11h30

On Divergence Information
Ashwin Nayak
Jeu 07 février 2008 - 11h30

Impossibility of a Quantum Speed-up with a Faulty Oracle
Oded Regev
Mar 29 janvier 2008 - 11h30