Home Page of Venkatesan Guruswami

Venkatesan Guruswami

Chancellor's Professor, Department of EECS
Senior Scientist, Simons Institute for the Theory of Computing
Professor, Department of Mathematics
University of California, Berkeley

Before joining UC Berkeley in Jan 2022, I was a faculty member in the Computer Science Dept at Carnegie Mellon University and enjoyed 13+ wonderful years in Pittsburgh (the comic has surely not aged well).

B.Tech, IIT Madras (1997); Ph.D., MIT (2001);
Miller Research Fellow, UC Berkeley (2001-02).

A special picture

Please consider submitting your top papers to the Journal of the ACM.

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.

Below is some further information about my two main research focuses:
- Error-correcting codes
  - Survey talk on ``List and local decoding": Slides, Video.
  - Survey talk on recent body of work on optimal rate list decoding by evading subspaces. Video of talk.
  - Video of short talk Non-Malleable Coding.
  - A older 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"

My research over the years has been generously supported by:
- National Science Foundation, via grants such as CAREER award, CDI.
- David and Lucile Packard Fellowship (2005)
- Sloan Research Fellowship (2005)

Students

Current PhD advisees:

Postdocs

Joao Ribeiro, August 2021-present.
Jonathan Mosheiff, Oct 2019-present.
Ankit Singh Rawat, Sep 2015-Aug 2016.
Mary Wootters, Sept 2014-July 2016.
Mahdi Cheraghchi, Sep. 2011-June 2013.
Krzysztof Onak, Simons postdoctoral fellow, 2010-12.
Rishi Saket, Sep'09-Aug'10.
Parikshit Gopalan, Mar'07-Jun'08.

Undergraduate/M.S:

Omar Alrabiah
Joshua Brakensiek

Winner of the 2018 CRA Outstanding Undergraduate Researcher award.

Ray Li. Honor's thesis (2017): New developments in coding against insertions and deletions
Zhen Zhou
Patrick Lin
Patrick Xia (M.S., 2013)

Graduated Ph.D.

Atri Rudra, Ph.D., 2007.
- Atri's award winning dissertation.
Prasad Raghavendra, Ph.D., 2009.
- Prasad's defense of his award winning thesis.
Ali Kemal Sinop, Ph.D., 2012.
- Ali's dissertation on SDP hierarchies in approximate optimization.
Yuan Zhou, Ph.D., 2014. (co-advised with R. O'Donnell)

Yuan's disseration on new directions in approximate optimization.

Carol Wang, Ph.D., 2015.

Dissertation: Beyond unique decoding: topics in error-correcting codes

Ameya Velingker, Ph.D., 2016.
- Dissertation: New Directions in Coding Theory: Capacity and Limitations
Euiwoong Lee, Ph.D., 2017.
- Dissertation: Optimal approximabilities beyond CSPs;
  Inaugural winner of Edmund M. Clarke Doctoral Dissertation Award

Vijay Bhattiprolu, Ph.D., 2019
- Dissertation: On the Approximability of Injective Tensor Norm
Nicolas Resch, Ph.D., 2020

Teaching

Spring 2021: 15-252: More Great Ideas in Theoretical Computer Science
Fall 2020: 15-455: Undergraduate complexity theory
Spring 2020: 15-252: More Great Ideas in Theoretical Computer Science
Fall 2019: 15-859FF: Coping with intractability: parameterized and fast-exponential algorithms
Spring 2019: 15-251: Great Ideas in Theoretical Computer Science
Fall 2018: 15-859Y: Coding Theory
Fall 2016: 15-251: Great Theoretical Ideas in Computer Science
Fall 2016: 15-751: A Theorist's Toolkit
Spring 2016: 15-503/859: Cryptotheory
Fall 2015: 15-855: Computational Complexity Theory
Fall 2014: 15-859Y: Coding Theory
Fall 2014: 15-251: Great Theoretical Ideas in Computer Science
Spr 2013: Information theory and its applications in theory of computation
Fall 2012: 15-251: Great Theoretical Ideas in Computer Science
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

Selected Professional Service

Editor-in-Chief, Journal of the ACM, Dec 2021-.
Editor, TheoretiCS , Dec 2021-.

Vice chair, IEEE Technical Committee on Mathematical Foundations of Computing, Feb 2022-.
Simons Institute Scientific Advisory Board, Feb 2020-Dec 2021.
arXiv moderator, cs.IT, 2018-.
President, Computational Complexity Foundation, July 2018-July 2021.
Editor-in-Chief, ACM Transactions on Computation Theory, Feb 2017-Nov 2019.
Program Committee Chair:
- ISIT 2018 (co-chair)
- FOCS 2015
- CCC 2012
Journal Editorial Boards:
- Journal of the ACM, 2015-2021.
- SIAM Journal on Computing, 2009-17.
- Research in the Mathematical Sciences, 2015-
- IEEE Transactions on Information Theory, 2010-14.
- ACM Transactions on Computation Theory, 2007-15.
Scientific Board, Electronic Colloquium on Computational Complexity
Co-organizer, Dagstuhl seminar, The constraint satisfaction problem: Complexity and Approximability, July 2015, June 2018, and May 2022.
Co-organizer, Simons Institute Program on Information Theory, Jan-May, 2015.
Board of Trustess and Awards Chair, Computational Complexity Foundation, Inc., 2014-16.
SIGACT Executive Committee Member (July 2012-15).
Co-organizer, Summer Thematic Program on Constraint Satisfaction, Fields Institute, July-Aug 2011.
Conference Program Committees:
- STOC 2022, FOCS 2019, ITCS 2019, STOC 2015, ISIT 2012, STOC 2011
- CCC 2010, SODA 2010, FSTTCS 2008, STOC 2008, ITW 2008, LATIN 2008
- APPROX 2007, ISIT 2006, CCC 2006, FSTTCS 2005, FOCS 2005, FOCS 2002.

You are visitor number to this page.