Composition de l'équipe
  Responsable
    

Activités de recherche
  Vérification
  Algorithmique
  Combinatoire
  Calcul quantique
  Complexité
  Théorie de la cryptographie

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
  Complexité des dynamiques des jeux
  Etude algorithmique et structuriel de graphes aretes-coloriées
  Calculs et communications quantiques avec des variables continues

Labeling schemes for bounded degree graphs
Noy Rotbart
Ven. 20 septembre 2013 - 14h00

Geometry behind Art : Tessellations, Reversibilities and Decompositions of Polyhedra
Jin Akiyama
Ven. 05 octobre 2012 - 14h30

Time-space tradeoffs for width-parameterized SAT
Periklis A. Papakonstantinou
Ven. 29 juin 2012 - 14h30

A new algorithm for the Orthogonal Packing Problem
Petru Valicov
Ven. 25 mai 2012 - 15h00

Un algorithme exponentiel pour l'étiquetage L(2,1) de graphes
Mathieu Liedloff
Ven. 25 mai 2012 - 14h00

A new graph parameter and its relation to approximation properties of graph H-colouring
Johan Thapper
Ven. 04 mai 2012 - 14h30

Finite obstructions to graph partitions
Pavol Hell
Ven. 13 avril 2012 - 14h30

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

Automated prediction of three-way junction topological families in RNA secondary structures
11 février 2012
Alexis Lamiable, Dominique Barth, Alain Denise, Franck Quessette, Sandrine Vial, Éric Westhof. Computational Biology and Chemistry 37 (2012) 1–5