Français Anglais
Accueil Annuaire Plan du site
Home > Groups > Research groups > Algorithms and Complexity (Algo)
Groups
Algorithms and Complexity (Algo)
Page no more maintained

as of 30 September 2013
please refer to the new team
GALaC


Research themes:
  • Algorithms, Complexity
  • Combinatorics and probabilistic methods
  • Logic and Complexity
  • Algorithmic Graph theory

Group Members
  Group leader
    MANOUSSAKIS Yannis

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

Seminars
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


Résultats majeurs
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

Software & patents