I am a postdoc at Harvard hosted by Prof. Demba Ba, Prof. Boaz Barak, Prof. Lucas Janson and Prof. Cengiz Pehlevan. Before this, I was a graduate student at the TOC group at MIT where I was advised by Prof. Ryan Williams.

My current research focusses on deep learning.

Publications (ML)

  • Beyond Implicit Bias: The Insignificance of SGD Noise in Online Learning.
    Nikhil Vyas*, Depen Morwani*, Rosie Zhao*, Gal Kaplun*, Sham Kakade, Boaz Barak
    Under Submission
  • Feature-Learning Networks Are Consistent Across Widths At Realistic Scales.
    Nikhil Vyas*, Alexander Atanasov*, Blake Bordelon*, Depen Morwani, Sabarish Sainathan, Cengiz Pehlevan
    NeurIPS 2023
  • On Privileged and Convergent Bases in Neural Network Representations.
    Davis Brown*, Nikhil Vyas*, Yamini Bansal
    Workshop on High-dimensional Learning Dynamics at ICML 2023
  • Provable Copyright Protection for Generative Models.
    Nikhil Vyas, Sham Kakade, Boaz Barak
    ICML 2023
  • Limitations of the NTK for Understanding Generalization in Deep Learning.
    Nikhil Vyas, Yamini Bansal, Preetum Nakkiran
    TMLR
  • Thwarting Adversarial Examples: An L_0-Robust Sparse Fourier Transform.
    Mitali Bafna*, Jack Murtagh*, Nikhil Vyas*
    NeurIPS 2018

    • Publications (Theory)

  • On Oracles and Algorithmic Methods for Proving Lower Bounds.
    Nikhil Vyas, Ryan Williams
    ITCS 2023
  • On the Number of Quantifiers as a Complexity Measure.
    Ronald Fagin, Jonathan Lenchner, Nikhil Vyas, Ryan Williams
    MFCS 2022
  • Optimal Fine-grained Hardness of Approximation of Linear Equations.
    Mitali Bafna, Nikhil Vyas
    ICALP 2021
  • Multi-Structural Games and Number of Quantifiers.
    Ronald Fagin, Jonathan Lenchner, Kenneth W. Regan, Nikhil Vyas
    LICS 2021
  • Fast Low-Space Algorithms for Subset Sum.
    Ce Jin, Nikhil Vyas, R. Ryan Williams
    SODA 2021
  • Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms.
    Nikhil Vyas, R. Ryan Williams
    STACS 2020
  • Near-Optimal Complexity Bounds for Fragments of the Skolem Problem.
    S. Akshay, Nikhil Balaji, Aniket Murhekar, Rohith Varma, Nikhil Vyas
    STACS 2020
  • Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse Graphs.
    Andrea Lincoln, Nikhil Vyas
    ITCS 2020
  • Efficient Constructions for Almost-Everywhere Secure Computation.
    Siddhartha Jayanti, Srinivasan Raghuraman, Nikhil Vyas
    EUROCRYPT 2020
  • On Super Strong ETH.
    Nikhil Vyas, Ryan Williams
    SAT 2019 [Best Paper Award]
  • Imperfect Gaps in Gap-ETH and PCPs.
    Mitali Bafna, Nikhil Vyas
    CCC 2019
  • Approximation Algorithms for Min-Distance Problems.
    Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu, Yuancheng Yu
    ICALP 2019
  • Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems.
    Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein
    ICALP 2019
  • Distribution-based objectives for Markov Decision Processes.
    S. Akshay, Blaise Genest, Nikhil Vyas
    LICS 2018
  • Complexity of Restricted Variants of Skolem and Related Problems.
    S. Akshay, Nikhil Balaji, Nikhil Vyas
    MFCS 2017
  • Faster space-efficient algorithms for subset sum and k-sum.
    Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas
    STOC 2017
  • On Regularity of Unary Probabilistic Automata.
    S. Akshay, Blaise Genest, Bruno Karelovic, Nikhil Vyas
    STACS 2016

    • Teaching

  • Advanced Complexity Theory. (MIT 6.841, Spring 2022)
    Teaching assistant to Professor Ryan Williams
  • Math for Computer Science. (MIT 6.042, Spring 2021)
    Teaching assistant to Zachary Abel, Professors Nancy Lynch and Ryan Williams
  • Learning Augmented Algorithms. (MIT 6.890, Spring 2019)
    Teaching assistant to Professors Costis Daskalakis and Piotr Indyk
  • Introduction to Computational Complexity. (IIT Bombay CS 721, Fall 2016)
    Teaching assistant to Professor Nutan Limaye.
  • Discrete Structures. (IIT Bombay CS 207, Fall 2015)
    Teaching assistant to Professor S. Akshay.