Composition de l'équipe
  Responsable
    MANOUSSAKIS Yannis

  Membres permanents
    FIORENZI Francesca
    GOUYOU-BEAUCHAMPS Dominique
    HIVERT Florent
    LAPLANTE Sophie
    MANOUSSAKIS Yannis
    PEYRONNET Sylvain

  Membres non-permanents
    ANGLES D'AURIAC Jean-Alexandre
    BOROZAN Valentin
    LERAYS Virginie
    MONTERO LEANDRO Pedro
    NARAYANAN Narayanan Potty
    STROZECKI Yann
    ZEITOUN Xavier

  Associés
    COHEN Johanne
    DE ROUGEMONT Michel
    VIAL Sandrine

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
  QRAC
  ICOMB
  CRYQ

Collaborations
  Ã‰quipe de Logique Mathématique Université Paris Diderot Paris 7
  GDR ICQ
  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
  Calculs et communications quantiques avec des variables continues
  Arbres proprement et faiblement arêtes-coloriées dans des graphes et multigraphes arêtes-coloriées
  Chaînes alternées dans les graphes arête-coloriés: k-linkage et arbres couvrants

Arbres enrichis
Daniele Gardy
Ven. 17 février 2012 - 14h30

Une preuve courte d'un résultat de choisissabilité dans les graphes planaires
Nathann Cohen
Ven. 03 février 2012 - 14h30

An Efficient Quantum Algorithm for some Instances of the Group Isomorphism Problem
Francois Le Gall
Jeu. 07 octobre 2010 - 11h00

Quantum State Tomography, Compressed Sensing, and Matrix Product States
Yi-Kai Liu
Mar. 28 septembre 2010 - 14h00

Better Bell inequality violations from theoretical computer science
Ronald de Wolf
Mar. 14 septembre 2010 - 15h30

Habilitation: Calcul Quantique
Julia Kempe
Mar. 14 septembre 2010 - 11h00

Information Cost Tradeoffs for AUGMENTED INDEX
Amit Chakrabarti
Mar. 07 septembre 2010 - 11h00

Strong NP-hardness of the Quantum Separability Problem
Sevag Gharibian
Mar. 17 août 2010 - 15h00

The positive definite Grothendieck problem with rank constraint
Jop Briet
Mar. 17 août 2010 - 11h00

Fast Robust Regression in Data Streams
David Woodruff
Mar. 13 juillet 2010 - 11h00

The detectability lemma and the area law
Umesh Vazirani
Ven. 09 juillet 2010 - 11h00

Multi-nonlocality : how can we characterize the quantum correlations of entangled independent sources ?
Denis Rosset
Jeu. 01 juillet 2010 - 11h00

Lower bounds for solving concurrent reachabiltiy games using strategy iteration
Peter Bro Miltersen
Mar. 29 juin 2010 - 14h00

Online Set Packing
Boaz Patt-Shamir
Mar. 29 juin 2010 - 11h00

Two-source extractors secure against quantum
Julia Kempe
Mar. 08 juin 2010 - 14h00

Lower Bounds for k-CLIQUE on Random Graphs
Ben Rossman
Ven. 28 mai 2010 - 14h00

Motifs et classes de permutations : le point de vue des arbres de décomposition
Mathilde Bouvel
Mar. 04 mai 2010 - 10h00

Expressions booléennes aléatoires et fonctions booléennes
Antoine Genitrini
Mar. 13 avril 2010 - 10h00

Interactive Hashing and BB84 states
Takeshi Koshiba
Mar. 30 mars 2010 - 11h30

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

Lower bounds for solving concurrent reachabiltiy games using strategy iteration
Peter Bro Miltersen
Ven. 29 juin 2001 - 14h00