Claire Mathieu

Contact Information

In Paris:
Email: cmathieu at
Office: Hauts du DI 10 (Escalier A, 3e etage)
45 rue d'Ulm, 75005 Paris, France
Phone: +33 1 44 32 33 28, Fax: +33 1 44 32 20 75

At Brown:
Email: Claire_Kenyon at
Office 555
Box 1910, Computer Science Department
Brown University
Providence, RI 02912
401-863-6066 (voice), 401-863-7657 (fax)

I am a CNRS director at Departement d'Informatique, Ecole Normale Superieure, Paris, France.

During a transition period, I am temporarily a part-time Member of the Brown CS department Theory group.


Unique games algorithm (Summary of the Arora-Barak-Steurer paper)

Metric 2011 Blog

A visit to Al Quds university


  • Spring 2013: co-teaching part-time with Franco Preparata, CSCI 2951-J, Special topics on advanced algorithms.
  • Spring 2012: CSCI 1570, Design and Analysis of Algorithms.
  • Fall 2011: CSCI 0170,, CS: an integrated introduction, taught in D hour (MWF 11-11:50).
  • Fall 2010: CSCI 2510, Approximation Algorithms, taught in M hour (Mondays 3-5:30).
  • Fall 2009: CSCI 2950-w, Online Algorithms.


    There are two directions to my research: combinatorial optimization with a focus on approximation algorithms; and probabilistic techniques for the design and analysis of algorithms. I also dabble with a variety of new directions: lift-and-project techniques to strengthen linear programs, algorithmic game theory, stochastic optimization, streaming algorithms.

    Online publications.


    Graduate applications: I regularly receive emails from students who might be interested in Brown. However, by university policy, I cannot look at resumes until receiving the application through the official channel.

    Summer internships and postdocs: I am usually gone for much of the summer, and have no funding for postdocs. Sorry! Please consider this posting as a reply to all emails enquiring about that.

    Current and former Phd Students

  • Hang Zhou (started PhD at ENS in 2012)
  • David Eisenstat (started PhD at Brown in 2009)
  • Warren Schudy (Brown, graduated 2010)
  • Aparna Das (Brown, graduated 2010)
  • Jeremy Barbay (Universite Paris-Sud, graduated 2002)
  • Nicolas Schabanel (ENS Lyon, graduated 2000)
  • Veronique Unger (ENS Lyon, took the "agregation" in Math and became a Math teacher).


  • Online Multicast with Egalitarian Cost Sharing (SPAA 2008),
  • Theorie Algorithmique des Jeux (INRIA 2008),
  • Presentation to new PHD students (2006, 2007).
  • Ski rental (Brown Theory lunch, 2007).
  • Low distortion maps (Yale 2006),
  • Oblivious medians via online bidding (Harvard 2006),
  • How to rank with few errors (Wics 2007, Toronto 2007),
  • Linear programming relaxations for Maxcut,
  • Profit-maximizing envy-free pricing (Bertinoro 2005),


    Vita and Publication list (last updated in 2010)


    Are you on this page because I ...
  • ... am co-organizing a Ecole de Printemps d'Informatique Théorique , March 26-30, 2012?
  • ... am co-organizing Dagstuhl workshop on Algorithms for Optimization Problems in Planar Graphs, October 13-18, 2013?
  • ... am editor of SiComp?