Venkatesan Guruswami

2005 Fellow

Current Institution: Carnegie Mellon University

Computer/Information Sciences

Visit Lab Website

About Venkatesan Guruswami's Work

Venkatesan Guruswami’s research interests span several topics in theoretical computer science including the theory of error-correcting codes, approximate solvability of optimization problems, pseudorandomness, communication complexity, and algebraic algorithms. Guruswami has a comprehensive body of research on “list decoding of error-correcting codes” to his credit. His work has shown how to achieve the fundamental limit of error-correction even in worst-case noise models. The insights from his work on coding theory have also led him to major advances in the construction of important “pseudorandom objects” such as expander graphs and randomness extractors. These pseudorandom objects are explicitly specified, but at the same time have the desirable properties of a typical random object in their class. Over the years, Guruswami has also made notable contributions to the theory of approximation algorithms using a wide range of techniques, proving strong, and often near-optimal, bounds on the approximate solvability of many fundamental optimization problems.

Awards and Achievements

Presburger Award (2012)

ACM Doctoral Dissertation Award (2002)

In the News

From Moonbounce to Hard Drives: Correcting More Errors Than Previously Thought Possible
National Science Foundation

Science Magazine