Home Page of Venkatesan Guruswami

The CMU theory group has an opening for a two year Simons postdoc (Fall 2012-Summer 2014). For details, visit http://theory.cs.cmu.edu/simons.html.

Venkatesan Guruswami

Associate Professor, Computer Science Dept, Carnegie Mellon University

B.Tech, IIT Madras (1997); Ph.D., MIT (2001);
Miller Research Fellow, UC Berkeley (2001-02);
Member, School of Mathematics, IAS, Princeton (2007-08).
Faculty member, Univ. of Washington, Seattle (2002-09).

Teaching during academic year 2011-12:

Spring 2012: 15-496/15-859X: Computer Science Theory for the Information Age
Fall 2011: 15-251: Great Theoretical Ideas in Computer Science

Contact

Research

Advising

Teaching

Brief bio

Committees

Research

Research Publications

Interests: Several topics in Theoretical Computer Science, including the theory of error-correcting codes, approximation algorithms & non-approximability, pseudorandomness, probabilistically checkable proofs, algebraic algorithms.

Brief description of my current research interests.

I am a member of the large & diverse theory group at CMU.
I am also affiliated with CMU's unique ACO program.

Below is some further information about my two main research focuses:
- Error-correcting codes
  - A survey appearing in CACM Mar'09 (in html format)
  - An NSF news article about our work on list decoding Reed-Solomon codes.
  - Article in Science Magazine on list (and local) decoding.
- Approximate solutions to NP-hard problems
  - Slides from a tutorial on Approximability of CSPs.

I gratefully acknowledge the support of
- NSF CDI Grant (2008)
- David and Lucile Packard Fellowship (2005)
- Sloan Research Fellowship (2005)
- NSF Career Award (2004)

Graduate Students

Currently (co)-advising:
Graduated Ph.D.
- Atri Rudra, Ph.D., 2007.
  - Currently on the faculty at Univ. at Buffalo.
  - Atri's award winning dissertation.
- Prasad Raghavendra, Ph.D., 2009.
  - Currently on the faculty at Georgia Tech.
  - Prasad's defense of his award winning thesis.

Postdocs

Mahdi Cheraghchi.
Rishi Saket, Sep'09-Aug'10.
- Currently at IBM T.J. Watson Research Center.
Parikshit Gopalan, Mar'07-Jun'08.
- Currently at MSR Silicon Valley.

Teaching

Spring'12: 15-496/15-859X: Computer Science Theory for the Information Age
Fall'11: 15-251: Great Theoretical Ideas in Computer Science
Spring'11: 15-855: An intensive introduction to computational complexity theory
Fall'10: Probability and Computing
Spring'10: Introduction to Coding Theory. The course blog
Spring'09: An Intensive Introduction to Computational Complexity Theory

At University of Washington:

Spring'07: Discrete Structures
Winter'07: Essential Complexity Theory
Autumn'06: Error-Correcting Codes: Constructions and Algorithms
Winter'06: Design and Analysis of Algorithms
Fall'05: The PCP Theorem and Hardness of Approximation
Spring'05: Introduction to Theory of Computation
Winter'05: Formal Models in Computer Science
Fall'04: Computability and Complexity
Spring'04: Discrete Structures
Fall'03: Computability and Complexity
Spring'03: Formal Models in Computer Science
Winter'03: Codes and Pseudorandom Objects
Fall'02: Computability and Complexity

Professional Service

Co-organizer, Summer Thematic Program on Constraint Satisfaction, Fields Institute, July-Aug 2011.
Associate Editor, SIAM Journal on Computing
Associate Editor, IEEE Transactions on Information Theory
Associate Editor, ACM Transactions on Computation Theory
Scientific Board, Electronic Colloquium on Computational Complexity
Area editor, Encyclopedia of Algorithms
Guest co-editor:
Conference Program Committees:
- ISIT 2012, July 1-6, 2012, Cambridge, MA.
- PC Chair, CCC 2012, Jun 26-29, 2012, Porto.
- STOC 2011, Jun 6-8, 2011, San Jose, CA.

You are visitor number to this page.

Research

Graduate Students

Currently (co)-advising:

Graduated Ph.D.

Postdocs

Teaching

Professional Service