On Regularity of Unary Probabilistic Automata. - S. Akshay 001; Blaise Genest; Bruno Karelovic; Nikhil Vyas 001 (STACS, 2016)

Complexity of Restricted Variants of Skolem and Related Problems. - S. Akshay 001; Nikhil Balaji; Nikhil Vyas 001 (MFCS, 2017)

Faster space-efficient algorithms for subset sum and k-sum. - Nikhil Bansal 001; Shashwat Garg; Jesper Nederlof; Nikhil Vyas 001 (STOC, 2017)

Distribution-based objectives for Markov Decision Processes. - S. Akshay 001; Blaise Genest; Nikhil Vyas 001 (LICS, 2018)

Thwarting Adversarial Examples: An L_0-Robust Sparse Fourier Transform. - Mitali Bafna; Jack Murtagh; Nikhil Vyas 001 (NeurIPS, 2018)

Super Strong ETH is False for Random k-SAT. - Nikhil Vyas 001 (CoRR, 2018)

Thwarting Adversarial Examples: An L0-RobustSparse Fourier Transform. - Mitali Bafna; Jack Murtagh; Nikhil Vyas 001 (CoRR, 2018)

Faster Space-Efficient Algorithms for Subset Sum, k-Sum, and Related Problems. - Nikhil Bansal 001; Shashwat Garg; Jesper Nederlof; Nikhil Vyas 001 (SIAM J. Comput., 2018)

Imperfect Gaps in Gap-ETH and PCPs. - Mitali Bafna; Nikhil Vyas 001 (CCC, 2019)

Approximation Algorithms for Min-Distance Problems. - Mina Dalirrooyfard; Virginia Vassilevska Williams; Nikhil Vyas 001; 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 001; Nicole Wein (ICALP, 2019)

Efficient Constructions for Almost-everywhere Secure Computation. - Siddhartha Jayanti; Srinivasan Raghuraman; Nikhil Vyas 001 (IACR Cryptol. ePrint Arch., 2019)

Results on a Super Strong Exponential Time Hypothesis. - Nikhil Vyas 001; Ryan Williams 001 (AAAI, 2020)

Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse Graphs. - Andrea Lincoln; Nikhil Vyas 001 (ITCS, 2020)

Near-Optimal Complexity Bounds for Fragments of the Skolem Problem. - S. Akshay 001; Nikhil Balaji; Aniket Murhekar; Rohith Varma; Nikhil Vyas 001 (STACS, 2020)

Optimal Fine-Grained Hardness of Approximation of Linear Equations. - Mitali Bafna; Nikhil Vyas 001 (ICALP, 2021)

Fast Low-Space Algorithms for Subset Sum. - Ce Jin 001; Nikhil Vyas 001; Ryan Williams 001 (SODA, 2021)

On Super Strong ETH. - Nikhil Vyas 001; R. Ryan Williams (J. Artif. Intell. Res., 2021)

On the Number of Quantifiers as a Complexity Measure. - Ronald Fagin; Jonathan Lenchner; Nikhil Vyas 001; R. Ryan Williams (MFCS, 2022)

Limitations of the NTK for Understanding Generalization in Deep Learning. - Nikhil Vyas 001; Yamini Bansal; Preetum Nakkiran (CoRR, 2022)

On the Benefits of Learning to Route in Mixture-of-Experts Models. - Nishanth Dikkala; Nikhil Ghosh; Raghu Meka; Rina Panigrahy; Nikhil Vyas 001; Xin Wang 016 (EMNLP, 2023)

On Provable Copyright Protection for Generative Models. - Nikhil Vyas 001; Sham M. Kakade; Boaz Barak (ICML, 2023)

Feature-Learning Networks Are Consistent Across Widths At Realistic Scales. - Nikhil Vyas 001; Alexander B. Atanasov; Blake Bordelon; Depen Morwani; Sabarish Sainathan; Cengiz Pehlevan (NeurIPS, 2023)

On Privileged and Convergent Bases in Neural Network Representations. - Davis Brown; Nikhil Vyas 001; Yamini Bansal (CoRR, 2023)

Empirical Limitations of the NTK for Understanding Scaling Laws in Deep Learning. - Nikhil Vyas 001; Yamini Bansal; Preetum Nakkiran (Trans. Mach. Learn. Res., 2023)

Satisfiability Algorithms and Connections between Algorithms and Circuit Lower Bounds - Nikhil Vyas 001 (2023)

Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms. - Nikhil Vyas 001; R. Ryan Williams (Theory Comput. Syst., 2023)

Beyond Implicit Bias: The Insignificance of SGD Noise in Online Learning. - Nikhil Vyas 001; Depen Morwani; Rosie Zhao; Gal Kaplun; Sham M. Kakade; Boaz Barak (ICML, 2024)

Distinguishing the Knowable from the Unknowable with Language Models. - Gustaf Ahdritz; Tian Qin; Nikhil Vyas 001; Boaz Barak; Benjamin L. Edelman (ICML, 2024)

Deconstructing What Makes a Good Optimizer for Language Models. - Rosie Zhao; Depen Morwani; David Brandfonbrener; Nikhil Vyas 001; Sham M. Kakade (CoRR, 2024)

Quasi-Linear Size PCPs with Small Soundness from HDX. - Mitali Bafna; Dor Minzer; Nikhil Vyas 001 (CoRR, 2024)

SOAP: Improving and Stabilizing Shampoo using Adam. - Nikhil Vyas 001; Depen Morwani; Rosie Zhao; Itai Shapira; David Brandfonbrener; Lucas Janson; Sham M. Kakade (CoRR, 2024)

On Oracles and Algorithmic Methods for Proving Lower Bounds. - Nikhil Vyas 001; Ryan Williams 001 (Electron. Colloquium Comput. Complex., 2024)

SOAP: Improving and Stabilizing Shampoo using Adam for Language Modeling. - Nikhil Vyas 001; Depen Morwani; Rosie Zhao; Itai Shapira; David Brandfonbrener; Lucas Janson; Sham M. Kakade (ICLR, 2025)

Mixture of Parrots: Experts improve memorization more than reasoning. - Samy Jelassi; Clara Mohri; David Brandfonbrener; Alex Gu; Nikhil Vyas 001; Nikhil Anand; David Alvarez-Melis; Yuanzhi Li; Sham M. Kakade; Eran Malach (ICLR, 2025)

A New Perspective on Shampoo's Preconditioner. - Depen Morwani; Itai Shapira; Nikhil Vyas 001; Eran Malach; Sham M. Kakade; Lucas Janson (ICLR, 2025)

How Does Critical Batch Size Scale in Pre-training? - Hanlin Zhang 002; Depen Morwani; Nikhil Vyas 001; Jingfeng Wu; Difan Zou; Udaya Ghai; Dean P. Foster; Sham M. Kakade (ICLR, 2025)

Deconstructing What Makes a Good Optimizer for Autoregressive Language Models. - Rosie Zhao; Depen Morwani; David Brandfonbrener; Nikhil Vyas 001; Sham M. Kakade (ICLR, 2025)

Quasi-Linear Size PCPs with Small Soundness from HDX. - Mitali Bafna; Dor Minzer; Nikhil Vyas 001; Zhiwei Yun (STOC, 2025)

Multi-Structural Games and Number of Quantifiers. - Ronald Fagin; Jonathan Lenchner; Kenneth W. Regan; Nikhil Vyas 001 (Log. Methods Comput. Sci., 2025)

Loss-to-Loss Prediction: Scaling Laws for All Datasets. - David Brandfonbrener; Nikhil Anand; Nikhil Vyas 001; Eran Malach; Sham M. Kakade (Trans. Mach. Learn. Res., 2025)

Connections between Schedule-Free Optimizers, AdEMAMix, and Accelerated SGD Variants. - Depen Morwani; Nikhil Vyas 001; Hanlin Zhang 002; Sham M. Kakade (CoRR, 2025)