About Mark Braverman's Work
My research focuses on core problems within theoretical computer science and their connections to areas outside of computer science. The unifying theme of my work is generating and applying new computational and algorithmic insights through interactions between these disciplines and theoretical computer science. Two major recent themes in our works have been distributed computation and mechanism design. Within distributed computation, we have been developing new information-theoretic techniques to provide tight bounds on core statistical tasks on distributed data. Mechanism design studies algorithms that are intended to coordinate self-interested agents (for example, an auction is a type of resource allocation mechanism). A particularly promising direction is on the interaction between learning theory and mechanism design. My group has initiated the study of “learning mechanisms”: where an algorithm is trying to learn from observations, but the observations come from strategic players (who might want to mislead the algorithm to gain an advantage).
Awards and Achievements
NSF CAREER award (2012)
Stephen Smale Prize from the Society for the Foundations of Computational Mathematics (2014)
European Mathematical Society Prize (2016)