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

Former students

  • 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

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