Vinayak M. Kumar

Hello! I am a fourth-year Ph.D. student in UT Austin's Computer Science Theory group. I'm very lucky to have David Zuckerman as my advisor, and to be graciously supported by a Jane Street Fellowship. I am interested in combinatorial and probabilistic problems in pseudorandomness and complexity theory, like hashing, coding theory, and circuit lower bounds.

Before joining UT Austin in 2021, I received my B.S. in mathematics and computer science at Caltech. I'm extremely grateful to have been mentored by Venkatesan Guruswami and Leonard Schulman during my undergraduate years.

Publications & Preprints

• Linear Hashing Is Optimal
  Michael Jaber, Vinayak M. Kumar, David Zuckerman
  STOC 2025 (to appear)
• New Pseudorandom Generators and Correlation Bounds Using Extractors
  Vinayak M. Kumar
  ITCS 2025 (ECCC) (arXiv) (Talk)
• Improved Circuit Lower Bounds and Quantum-Classical Separations
  Sabee Grewal, Vinayak M. Kumar
  Preprint (ECCC) (arXiv)
• Relaxed Local Correctability from Local Testing
  Vinayak M. Kumar, Geoffrey Mon
  STOC 2024 (ECCC) (arXiv) (STOC Proceedings) (My Talk) (Geoff's Talk)
  Danny Lewin Best Student Paper Award
  Invited to the SICOMP Special Issue for STOC 2024
• Tight Correlation Bounds for Circuits Between AC0 and TC0
  Vinayak M. Kumar
  CCC 2023 (ECCC) (arXiv) (CCC Proceedings)
• On the Rational Degree of Boolean Functions and Applications
  Vishnu Iyer, Siddhartha Jain, Matt Kovacs-Deak, Vinayak M. Kumar, Luke Schaeffer, Daochen Wang, Michael Whitmeyer
  Preprint (arXiv)
• Pseudobinomiality of the Sticky Random Walk
  Venkatesan Guruswami, Vinayak M. Kumar
  ITCS 2021 (ECCC) (ITCS Proceedings) (My ITCS Talk)
• Condition Number Bounds for Causal Inference
  Spencer Gordon, Vinayak M. Kumar, Leonard Schulman, Piyush Srivastava
  UAI 2021 (UAI Proceedings) (Piyush's Simons Talk)

Teaching

• CS 395T: Spectral Graph Theory (Spring 2025)
• CS 395T: Pseudorandomness (Fall 2023)
• CS 388C: Combinatorics and Graph Theory (Spring 2023)

• CS 151: Complexity Theory (Spring 2021)
• CS 139: Design and Analysis of Algorithms (Winter 2021)
• CS 38: Introduction to Algorithms (Spring 2020)
• CS 21: Complexity Theory (Winter 2020)
• Ma 0: Transition to Mathematical Proofs (Summer 2020)