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 2day workshop will be organized December 78, 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, 10am12am.

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), coorganized by Iordanis Kerenidis
 Workshops on Inference Problems (March 7  18), including talks on Property Testing and Streaming algorithms
Former students
 Vincent CohenAddad, 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 MallmannTrenn, now postdoc at MIT
 Arnaud de Mesmay, now CNRS research scientist at GipsaLab, Grenoble
 Hang Zhou, now assistant professor at Ecole Polytechnique, Palaiseau
Former postdocs
 Holger Dell, now researcher at Saarland University
 Lila Fontes, now assistant professor at Swarthmore College
 Reut Levi, now lecturer at Weizmann Institute of Science
 Tatiana Starikovskaya, now assistant professor at ENS Paris