Some of our key results

We designed the first algorithm for recommendation systems that runs in time polylogarithmic in the dimensions of the matrix and provides an example of a quantum machine learning algorithm for a real world application (ITCS'17).
We established several tight separations between some measures of deterministic, randomized and quantum query complexity (STOC’16). In particular our separations disproved a conjecture of Saks and Wigderson from 1986.
We formally defined and studied the glass ceiling effect in social networks and proposed a natural mathematical model, called the biased preferential attachment model, that partially explains the causes of the glass ceiling effect (ITCS’15).
How much cutting is needed to simplify the topology of a surface? We provide bounds for several important instances of this question (SOCG'14). In particular we prove a conjecture of Przytycka and Przytycki from 1993.
First implementation of a quantum protocol for coin flipping, with security unconditionally stronger than in any classical protocol (Nature Communication 2014).

Lectures and Workshops

Closing workshop: In collaboration with a CNRS bilateral collaboration (PICS), a 2-day workshop will be organized December 7-8, 2017 at IRIF, room 3052. See meetings.
Claire Mathieu will give a sequence of lectures on Algorithms overlapping RDAM topics at Collège de France from November 28, 2017 to January 30, followed by a seminar every Tuesday morning, 10am-12am.
Zvi Lotker got the FSMP Chair, and gave his Chair lecture on the Mathematics and Algorithms of Social Networks at Institut Henry PoinCaré from November 2015 to January 2016
Claire Mathieu designed a Coursera MOOC on Approximation Algorithms
IHP trimester on Nexus of Information and Computation theories: January to March 2016. Two workshops are hightly related to the RDAM project:
- Workshop on Fundamental Inequalities and Lower Bounds (February 15 – 26), co-organized by Iordanis Kerenidis
- Workshops on Inference Problems (March 7 - 18), including talks on Property Testing and Streaming algorithms

Vincent Cohen-Addad, now CNRS research scientist at Université Pierre et Marie Curie, Paris
Nathanaël François, now teacher in Mathematics
Mathieu Lauriere, now postdoc at Princeton
Marc Renault, now assistant professor at University of Wisconsin
Virginie Lerays, now teacher in Mathematics (classes préparatoires)
Frederik Mallmann-Trenn, now postdoc at MIT
Arnaud de Mesmay, now CNRS research scientist at Gipsa-Lab, Grenoble
Hang Zhou, now assistant professor at Ecole Polytechnique, Palaiseau