My work concerns theoretical computer science, which seeks to provide fundamental understanding of many settings of computer science. In last few years I have focused on machine learning. Many current machine learning algorithms lack provable guarantees on one or more of the following metrics: solution quality, sample complexity, running time. The goal of my work is to provide algorithms with such performance guarantees. This can involve designing fundamentally new algorithms, or proving such guarantees for existing algorithms. Recent work includes touches upon topic models, sentence embeddings, generative adversarial nets, quantification of “effective capacity” of deep nets, etc.

Awards and Achievements

  • ACM-EATCS Gödel Prize ( 2001)
  • ACM-EATCS Gödel Prize ( 2010)
  • Sloan Fellowship ( 1996)
  • Packard Fellowship ( 1997)
  • ACM Infosys Foundation Award in the Computing Sciences ( 2012)
  • D. R. Fulkerson Prize ( 2012)
  • Simons Investigator Award ( 2012)
  • National Academy of Science
  • American Academy of Arts and Sciences
  • ACM Prize in Computing