Home Page of Venkatesan Guruswami

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).
Asst./Assoc. Professor, Univ. of Washington, Seattle (2002-09).

Recent teaching:

Currently teaching (Spr 2013): Information theory and its applications in theory of computation

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

Contact

CV

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 highlight on our work on list decoding with optimal redundancy.
  - 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.
  - Slides from 2011 survey talk "PCPs in the last decade"

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 faculty at Univ. at Buffalo.
  - Atri's award winning dissertation.
- Prasad Raghavendra, Ph.D., 2009.
  - Currently faculty at UC Berkeley.
  - Prasad's defense of his award winning thesis.
- Ali Kemal Sinop, Ph.D., 2012.
  - Currently a Princeton Univ./Institute for Advanced Study postdoc.
Postdocs
- Mahdi Cheraghchi, Sep. 2011-present.
- 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

SIGACT Executive Committee Member (since July 2012).
CCC Conference Committee, July 2012-
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.