Vinayak M. Kumar

Hello! I am a Research Fellow at the Simons Institute for the Pseudorandomness and High-Dimensional Expansion Program. In 2027, I will be an NSF Postdoc at UC Berkeley, hosted by Venkatesan Guruswami.

I received my Ph.D. from UT Austin, where I was very lucky to be advised by David Zuckerman and to be generously funded by a Jane Street Fellowship. Before that, I received my B.S. in mathematics and computer science at Caltech.

I am interested in combinatorial and probabilistic problems in pseudorandomness and complexity theory, like hashing, coding theory, and circuit complexity.

Publications & Preprints

• Covering (F_2)^n with Hamming Balls
  Michael Jaber, Vinayak M. Kumar
  Preprint
  arXiv


• Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
  Elena Grigorescu, Vinayak M. Kumar, Peter Manohar, Geoffrey Mon
  STOC 2026
  ECCC | arXiv


• Most Juntas Saturate the Hardcore Lemma
  Vinayak M. Kumar
  SOSA 2026
  ECCC | arXiv | SOSA Proceedings


• Linear Hashing Is Optimal
  Michael Jaber, Vinayak M. Kumar, David Zuckerman
  STOC 2025
  Invited to TheoretiCS
ECCC | arXiv | STOC Talk (40 min) | UWaterloo Talk (1 hr) | CMU 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
  SICOMP Special Issue for STOC 2024
ECCC | arXiv | SICOMP | 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: Graduate Complexity Theory (Spring 2021)
• CS 139: Graduate Algorithms (Winter 2021)
• CS 38: Introduction to Algorithms (Spring 2020)
• CS 21: Introduction to Complexity Theory (Winter 2020)
• Ma 0: Transition to Mathematical Proofs (Summer 2020)