University of California, Berkeley

Venkatesan Guruswami

Chancellor's Professor, Department of EECS

Director, Simons Institute for the Theory of Computing

Professor, Department of Mathematics

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

Fellow of the ACM, IEEE, and AMS; Simons Investigator; Guggenheim Fellow.

Before moving to UC Berkeley in Jan 2022, I spent 13+ enjoyable years in the CS Dept. at Carnegie Mellon.

Contact Publications CV Brief bio

A special picture

Teaching in Spring 2026: Proving TCS and Math Theorems using Lean.

Journal of the ACM: I am serving as Editor-in-Chief; please consider submitting your top papers to JACM.

Simons Institute: Q&A; Theory at the Institute and Beyond columns: July 2023, Feb 2023, Oct 2022.

Research

Research PublicationsBrowse the publications page

Interests: Several topics in Theoretical Computer Science, including coding theory, complexity of approximate optimization & constraint satisfaction, quantum error-correction, pseudorandomness, computational complexity, and related mathematics. Also intrigued by AI-for-TCS and Lean formalization of TCS results.
Below is some older information about two of my main research focuses:
- Error-correcting codes
  - Survey talk on ``List and local decoding": Slides, Video.
  - Survey talk on optimal rate list decoding by evading subspaces.
  - An NSF highlight on our work on list decoding with optimal redundancy.
  - 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"

Current Advising

Current PhD advisees, current postdoc, and undergraduate project.

Current PhD advisees:

Omar Alrabiah
Louis Golowich
Meghal Gupta
Shilun Li
Xuandi Ren
Mihir Singhal (co-advised with Jelani Nelson)

Current postdoc

Joshua Brakensiek, Aug 2024-.

Undergraduate project

Formalizing Theoretical Computer Science in Lean

Former Advisees and Postdocs

Former postdocs, undergraduate and M.S. researchers, and graduated PhD students.

Former postdocs

Hsin-Po Wang, Oct 2022-May 2024.
Sai Sandeep, Sep 2022-May 2023.
Ray Li, Aug 2022-Aug 2023.
Joao Ribeiro, August 2021-Jan 2023.
Jonathan Mosheiff, Oct 2019-Mar 2022.
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:

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.
- Dissertation: List decoding and property testing of error-correcting codes; William Chan Memorial Dissertation Award recipient.
Prasad Raghavendra, Ph.D., 2009.
- Dissertation: Approximating NP-hard problems: Efficient algorithms and their limits; William Chan Memorial Dissertation Award recipient.
Ali Kemal Sinop, Ph.D., 2012.
- Dissertation: Graph partitioning and semidefinite programming hierarchies
Yuan Zhou, Ph.D., 2014. (co-advised with R. O'Donnell)

Dissertation: New Directions in Approximation Algorithms and Hardness of Approximation

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
- Dissertation: List-Decodable Codes: (Randomized) Constructions and Applications
Andrii Riazanov, Ph.D., 2022
- Dissertation: Polar Codes with Near-Optimal Convergence to Channel Capacity
Sai Sandeep, Ph.D., 2022
- Dissertation: New Directions in Inapproximability: Promise Constraint Satisfaction Problems and Beyond
Peter Manohar, Ph.D., 2024
- Dissertation: New Spectral Techniques in Algorithms, Combinatorics, and Coding Theory: The Kikuchi Matrix Method
Pranav Trivedi, Ph.D., 2026
- Dissertation: Quantum Hierarchical Locally Recoverable Codes

Teaching

Current and past courses, with links to course pages and materials where available.

Fall 2022: Advances in Error-Correcting Codes

At Carnegie Mellon:

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 (these pages are unfortunately no longer available):

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

Editorial roles, conference organization, program committees, and advisory 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-.
International Scientific Advisory Committee member for ETH-ITS.
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.