Français Anglais
Accueil Annuaire Plan du site
Accueil > Equipes > Toutes les équipes > Algorithmique et Complexité (Algo)
Equipes
Algorithmique et Complexité (Algo)
Page non-maintenue

depuis le 30 septembre 2013
se référer à la nouvelle équipe
GALaC


Thèmes de recherche :
  • Algorithmique, Complexité
  • Combinatoire et méthodes probabilistes
  • Logique et Complexité
  • Théorie Algorithmique de Graphes

Composition de l'équipe
  Responsable
    MANOUSSAKIS Yannis

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

Séminaires
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


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

Logiciels et brevets