My research interests span several topics in theoretical computer science including the theory of error-correcting codes, approximate solvability of hard optimization problems, explicit combinatorial constructions and pseudorandomness, and computational complexity theory. I have a comprehensive body of research on “list decoding of error-correcting codes” and have shown how to achieve the fundamental limit of error-correction even against worst-case noise models, demonstrating that a variant of the widely used Reed-Solomon codes can achieve the optimal trade-off between information rate and number of worst-case errors that can be corrected.

Awards and Achievements

  • Presburger Award ( 2012)
  • ACM Doctoral Dissertation Award ( 2002)
  • ACM Fellow ( 2017)
  • International Congress of Mathematicians Invited Speaker ( 2010)

In the News