ACADEMIA

The European Association for Theoretical Computer Science has named Venkatesan Guruswami, associate professor of computer science, and Mihai Pătraşcu of AT&T Labs as joint recipients of its 2012 Presburger Award for young scientists.

Since 2010, EATCS has conferred the award each year to a young scientist (in exceptional cases to several young scientists) for outstanding contributions in theoretical computer science, documented by a published paper or a series of published papers.

Guruswami, who joined the Carnegie Mellon Computer Science Department in 2009, has contributed cornerstone results to the theory of list decoding of error-correcting codes.  Such codes safeguard data against the adverse effects of noise and enable reliable storage and communication of digital information. They are crucial to the error-free operation of computer hard drives, digital televisions, cell phones, and satellite communications. Guruswami's work culminated in the creation, with former student Atri Rudra, of error-correcting codes with the best possible trade-off between the redundancy introduced in the data and the amount of errors corrected, answering a 50-year-old problem in coding theory.

His work, which he began with his PhD advisor Madhu Sudan at MIT, earlier gave a new error-correction algorithm for the classical and widely deployed Reed-Solomon codes, showing that it is possible to correct many more errors in these and related codes than previously considered possible. That discovery led to new methods to make digital communications more robust by enabling the detection of weaker signals in noisy environments.

In recent years, the insights from his work on error correction have led him and others to key advances in the subject of "pseudorandomness" such as the construction of sparse yet highly connected network structures and methods to purify a defective source of random bits.  Such pseudorandom objects are explicitly specified, but at the same time have the desirable properties of a typical random object in their class, and thus find many applications.

Several of these results were made possible by establishing deep and novel connections between computational complexity, coding theory, randomness and computation.

Guruswami maintains a very broad research program spanning many topics of theoretical computer science. Over the years, he has also made notable contributions to the theory of approximation algorithms using a wide range of techniques, proving strong bounds on the approximate solvability of several fundamental and widely studied optimization problems.

Earlier honors to Guruswami include an invited lecture at the 2010 International Congress of Mathematicians, a David and Lucile Packard Fellowship for Science and Engineering, an Alfred P. Sloan Foundation Fellowship, a National Science Foundation Early Career Development Award, and the Association for Computing Machinery Doctoral Dissertation Award.