Rationale
Our project consists in joining the strengths of experts in both randomized and quantum computation. Our global objective is to make progress on both quantum and probabilistic computation, and also, by joining forces, to ensure that the flow of techniques goes in both directions, from randomized computation to quantum and back.
In randomized algorithms, our emphasis is on data-intensive models with restricted data access where randomization and sometimes approximation are fundamental tools. The areas we will cover are Property Testing, Streaming Algorithms, Online Algorithms, and Algorithmic Game Theory.
In quantum computation, we will continue to work on algorithms, especially for the Hidden Subgroup Problem and Vector Lattice Problems, and also on Quantum Walk based algorithms, on Quantum Query Complexity lower bounds, Complexity, Quantum Information and Communication.
At the intersection of quantum and randomized computation, our goal is to study Locally Decodable Codes, Communication Complexity, and Circuit Lower Bounds.
Work packages
RANDOMIZED ALGORITHMS
- Property Testing and Streaming Algorithms
- Online Algorithms
- Algorithmic Game Theory
QUANTUM COMPUTATION
- Quantum Algorithms
- Quantum Lower Bounds and Complexity
- Quantum Information and Communication
INTERACTION BETWEEN CLASSICAL AND QUANTUM COMPUTATION
- Locally Decodable Codes
- Classical and Quantum Communication Protocols
- Circuit Lower Bounds
Budget "fonctionnement", 2009-12: 420 k€
The following repartition may be updated further.
"Personnel": 220 k€
- Postdocs: 2 years (96 k€)
- PhD: 3 years (108 k€)
- Others (internships): 16 k€
"Autres dépenses": 200 k€
- Travels and Invitations: 104 k€
- Computers and small Equipment: 80 k€
- Management: 16 k€