Mark Braverman

I am now at Princeton University. My new homepage is here.

I am interested in complexity theory, the theory of real computation, machine learning, algorithms, game theory, and applications of computer science in healthcare and medicine.

My e-mail address:, replacing "#######" with "mbraverm"




All papers

By topic (with some overlap)

  Complexity theory
  Algorithms and random structures
  Economics, algorithmic game theory
  Computational Biology and Medicine
  Computability and complexity in analysis and dynamics

Book: Computability of Julia Sets
  Mark Braverman, Michael Yampolsky
    Springer, 2008
  [Amazon]   [Springer]

Selected recent papers

Monotonicity and Implementability
  Itai Ashalgi, Mark Braverman, Avinatan Hassidim, Dov Monderer
    Econometrica, forthcoming [pdf]
How to compress interactive communication
  Boaz Barak, Mark Braverman, Xi Chen, Anup Rao
    STOC'10, invited to the special issue of SICOMP [pdf]
    Previous version [ECCC]
Sorting from Noisy Information
  Mark Braverman, Elchanan Mossel
    Submitted [arXiv] [bib]


Last year, I was on the PC of FOCS'09 and on the PC of CCA'09.

Older links

Computability and Complexity in Analysis and Dynamics Seminar page

Theory Student Seminar is now organized by Siavosh Benabbas