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
  ECCC | arXiv | STOC Talk (40 min) | UWaterloo Talk (1 hr)


• New Pseudorandom Generators and Correlation Bounds Using Extractors
  Vinayak M. Kumar
  ITCS 2025
  ECCC | arXiv | ITCS Talk (25 min)


• 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
  Danny Lewin Best Student Paper Award
  Invited to the SICOMP Special Issue for STOC 2024
ECCC | arXiv | STOC Proceedings | STOC Talk (25 min) | Geoff's Simons Talk (40 min)


• 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, Robin Kothari 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 | ITCS Talk (30 min)


• Condition Number Bounds for Causal Inference
  Spencer Gordon, Vinayak M. Kumar, Leonard Schulman, Piyush Srivastava
  UAI 2021
  UAI Proceedings | Piyush's Simons Talk (30 min)

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)