Group Members
  Group leader
    

Research activities
  Verification
  Algorithms
  Combinatory
  Quantum computation
  Complexity
  Theoretical cryptography

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
  Random generation: models, methods and algorithms
  Quantum algorithms and complexity theory

Recent Ph.D. dissertations & faculty habilitations
  Complexité des dynamiques des jeux
  Graphs and Colors: Edge-colored graphs, edge-colorings and proper connections
  Calculs et communications quantiques avec des variables continues

Labeling schemes for bounded degree graphs
Noy Rotbart
20 September 2013 14h00

Geometry behind Art : Tessellations, Reversibilities and Decompositions of Polyhedra
Jin Akiyama
5 October 2012 14h30

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

A new algorithm for the Orthogonal Packing Problem
Petru Valicov
25 May 2012 15h00

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

A new graph parameter and its relation to approximation properties of graph H-colouring
Johan Thapper
4 May 2012 14h30

Finite obstructions to graph partitions
Pavol Hell
13 April 2012 14h30

Arbres enrichis
Daniele Gardy
17 February 2012 14h30

Une preuve courte d'un résultat de choisissabilité dans les graphes planaires
Nathann Cohen
3 February 2012 14h30

An Efficient Quantum Algorithm for some Instances of the Group Isomorphism Problem
Francois Le Gall
7 October 2010 11h00

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

Better Bell inequality violations from theoretical computer science
Ronald de Wolf
14 September 2010 15h30

Habilitation: Calcul Quantique
Julia Kempe
14 September 2010 11h00

Information Cost Tradeoffs for AUGMENTED INDEX
Amit Chakrabarti
7 September 2010 11h00

Strong NP-hardness of the Quantum Separability Problem
Sevag Gharibian
17 August 2010 15h00

The positive definite Grothendieck problem with rank constraint
Jop Briet
17 August 2010 11h00

Fast Robust Regression in Data Streams
David Woodruff
13 July 2010 11h00

The detectability lemma and the area law
Umesh Vazirani
9 July 2010 11h00

Multi-nonlocality : how can we characterize the quantum correlations of entangled independent sources ?
Denis Rosset
1 July 2010 11h00

Lower bounds for solving concurrent reachabiltiy games using strategy iteration
Peter Bro Miltersen
29 June 2010 14h00

Online Set Packing
Boaz Patt-Shamir
29 June 2010 11h00

Two-source extractors secure against quantum
Julia Kempe
8 June 2010 14h00

Lower Bounds for k-CLIQUE on Random Graphs
Ben Rossman
28 May 2010 14h00

Motifs et classes de permutations : le point de vue des arbres de décomposition
Mathilde Bouvel
4 May 2010 10h00

Expressions booléennes aléatoires et fonctions booléennes
Antoine Genitrini
13 April 2010 10h00

Interactive Hashing and BB84 states
Takeshi Koshiba
30 March 2010 11h30

Scheduling strategies for efficient interruptible algorithms
Spyros Angelopoulos
9 March 2010 11h00

Evasiveness and the Music of Primes
Raghav Kulkarni
3 March 2010 14h00

On the performance of approximate equilibria in congestion games
Giorgos Christodoulou
12 February 2010 11h00

Universal Cycles, 2-Radius Sequences, and Fetching Huge Objects into Small Memory
Yeow Meng CHEE
4 February 2010 14h30

Destructive rule-based properties and first-order logic
David Duris
4 February 2010 13h30

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

An Efficient Algorithm for Replicating Data in Modern Networks
Mauro Sozio
24 November 2009 14h00

Classical and Quantum Fanouts have the same Power
Simon Perdrix
12 November 2009 14h00

Information Flow in Secret Sharing Protocols
Damian Markham
5 November 2009 14h00

Tight bound for Gap Hamming Distance
Oded Regev
15 October 2009 14h00

Using Merlin to Estimate Histograms and Recursively Find Collisions, with Applications
David Xiao
1 October 2009 14h00

SZK Proofs for Black Box Group Problems
Bireswar Das
17 September 2009 14h00

On quantum mechanics over the reals
Matthew McKague
15 September 2009 11h30

Network Games with Quantum Strategies
Giannicola Scarpa
7 September 2009 11h30

Two-message quantum interactive proofs are in PSPACE.
Rahul Jain
9 July 2009 14h00

Correlation Clustering with Noisy Input.
Claire Mathieu
9 July 2009 11h30

Approximate Clustering without the Approximation Algorithm
Anupam Gupta
25 June 2009 10h00

An introduction to "continuous variable" quantum information
Barry Sanders
23 June 2009 15h30

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

Online Scheduling of Bounded Length Jobs to Maximize Throughput
Christoph Durr
11 June 2009 11h30

Des piles de sable aux automates de sable
Benoît Masson
7 May 2009 14h30

Hidden Polynomial Function Graphs
THOMAS DECKER
7 May 2009 11h30

Couplages parfaits dans les graphes cubiques
Louis Esperet
30 April 2009 14h00

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

TBA
Marion Le Gonidec
9 April 2009 14h00

Analyse statistique pour Markov Decision Processes et Automates Probabilistes
Mathieu Tracol
9 April 2009 11h30

Autour des surpartitions et des identités de type Rogers-Ramanujan
Olivier Mallet
2 April 2009 11h30

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

Unique Games with Entangled Provers are Easy
Oded Regev
26 February 2009 11h30

Efficient Isomorphism Testing for a Class of Group Extensions
Francois le Gall
20 February 2009 14h00

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

Approximation Algorithms on Bounded Dimensional Metric Spaces
Hubert Chan
18 December 2008 11h30

Rounding Parallel Repetitions of Unique Games
David Steurer
11 December 2008 11h30

On unconditional deterministic polynomial factorization over finite fields
Gabor Ivanyos
9 December 2008 11h30

Total positivity, matroids, and polytopes
Alex Postnikov
27 November 2008 11h30

Information Theoretic Approaches to Whole Genome Phylogenies
Benny Chor
13 November 2008 11h30

Property Testing in the Underlying Graph Model
Oded Lachish
6 November 2008 11h30

Finding optimal flow efficiently
Simon Perdrix
30 October 2008 11h30

On the hitting times of quantum versus random walks
Peter Richter
16 October 2008 11h30

Random algorithms for recognizing black-box groups
Peter P. Palfy
2 October 2008 11h30

Expander Flows, Graph Spectra and Graph Separators
Umesh Vazirani
1 July 2008 15h00

Sampling-Based Algorithms for Dimension Reduction
Amit Deshpande
1 July 2008 11h30

Making Classical Zero Knowledge Protocols Secure Against Quantum Attacks
Pranab Sen
26 June 2008 11h30

Molecular algorithms: combining efficiency with robustness
Ashish Goel
20 June 2008 11h30

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

Lower Bounds for Satisfiability and Related Problems
Dieter van Melkebeek
5 June 2008 14h00

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

Mechanism design for scheduling unrelated machines
Elias Koutsoupias
19 May 2008 11h30

Loss-tolerant quantum coin flipping
Gilles Brassard
9 May 2008 14h30

Quantum Cellular Automata
Vincent Nesme
29 April 2008 11h30

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

Cuts, Embeddings and Flows
Nisheeth Vishnoi
10 April 2008 11h30

Mixing on Random Graphs
Allan Sly
3 April 2008 11h30

Hierarchical Graph Decompositions for Minimizing Congestion
Harald Raecke
20 March 2008 11h30

Design and Analysis of Classic and Quantum Network Coding
Kazuo Iwama
25 February 2008 16h30

PSPACE has one round quantum multiprover interactive proofs
Keiji Matsumoto
25 February 2008 15h05

Entanglement and Multi-Prover Interactive Proof Systems
Hirotada Kobayashi
25 February 2008 14h00

Underapproximation for Model-Checking Based on Universal Circuits
Arie Matsliah
18 February 2008 11h00

On divergence Information (Lecture 2)
Ashwin Nayak
14 February 2008 11h30

On Divergence Information
Ashwin Nayak
7 February 2008 11h30

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

Lower bounds for solving concurrent reachabiltiy games using strategy iteration
Peter Bro Miltersen
29 June 2001 14h00

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