Nikhil Vyas

According to our database, Nikhil Vyas authored at least 37 papers between 2016 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

On Oracles and Algorithmic Methods for Proving Lower Bounds.

Nikhil Vyas, Ryan Williams

Electron. Colloquium Comput. Complex., 2024

How Does Critical Batch Size Scale in Pre-training?

Hanlin Zhang, Depen Morwani, Nikhil Vyas, Jingfeng Wu, Difan Zou, Udaya Ghai, Dean P. Foster, Sham M. Kakade

CoRR, 2024

Mixture of Parrots: Experts improve memorization more than reasoning.

Samy Jelassi, Clara Mohri, David Brandfonbrener, Alex Gu, Nikhil Vyas, Nikhil Anand, David Alvarez-Melis, Yuanzhi Li, Sham M. Kakade, Eran Malach

CoRR, 2024

SOAP: Improving and Stabilizing Shampoo using Adam.

Nikhil Vyas, Depen Morwani, Rosie Zhao, Itai Shapira, David Brandfonbrener, Lucas Janson, Sham M. Kakade

CoRR, 2024

Quasi-Linear Size PCPs with Small Soundness from HDX.

Mitali Bafna, Dor Minzer, Nikhil Vyas

CoRR, 2024

Deconstructing What Makes a Good Optimizer for Language Models.

Rosie Zhao, Depen Morwani, David Brandfonbrener, Nikhil Vyas, Sham M. Kakade

CoRR, 2024

A New Perspective on Shampoo's Preconditioner.

Depen Morwani, Itai Shapira, Nikhil Vyas, Eran Malach, Sham M. Kakade, Lucas Janson

CoRR, 2024

Distinguishing the Knowable from the Unknowable with Language Models.

Gustaf Ahdritz, Tian Qin, Nikhil Vyas, Boaz Barak, Benjamin L. Edelman

Proceedings of the Forty-first International Conference on Machine Learning, 2024

Beyond Implicit Bias: The Insignificance of SGD Noise in Online Learning.

Nikhil Vyas, Depen Morwani, Rosie Zhao, Gal Kaplun, Sham M. Kakade, Boaz Barak

Proceedings of the Forty-first International Conference on Machine Learning, 2024

2023

Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms.

Nikhil Vyas, R. Ryan Williams

Theory Comput. Syst., February, 2023

Satisfiability Algorithms and Connections between Algorithms and Circuit Lower Bounds

Nikhil Vyas

PhD thesis, 2023

Empirical Limitations of the NTK for Understanding Scaling Laws in Deep Learning.

Nikhil Vyas, Yamini Bansal, Preetum Nakkiran

Trans. Mach. Learn. Res., 2023

On Privileged and Convergent Bases in Neural Network Representations.

Davis Brown, Nikhil Vyas, Yamini Bansal

CoRR, 2023

Feature-Learning Networks Are Consistent Across Widths At Realistic Scales.

Nikhil Vyas, Alexander B. Atanasov, Blake Bordelon, Depen Morwani, Sabarish Sainathan, Cengiz Pehlevan

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

On Provable Copyright Protection for Generative Models.

Nikhil Vyas, Sham M. Kakade, Boaz Barak

Proceedings of the International Conference on Machine Learning, 2023

On the Benefits of Learning to Route in Mixture-of-Experts Models.

Nishanth Dikkala, Nikhil Ghosh, Raghu Meka, Rina Panigrahy, Nikhil Vyas, Xin Wang

Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, 2023

2022

Limitations of the NTK for Understanding Generalization in Deep Learning.

Nikhil Vyas, Yamini Bansal, Preetum Nakkiran

CoRR, 2022

On the Number of Quantifiers as a Complexity Measure.

Ronald Fagin, Jonathan Lenchner, Nikhil Vyas, R. Ryan Williams

Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022

2021

On Super Strong ETH.

Nikhil Vyas, R. Ryan Williams

J. Artif. Intell. Res., 2021

Fast Low-Space Algorithms for Subset Sum.

Ce Jin, Nikhil Vyas, Ryan Williams

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Multi-Structural Games and Number of Quantifiers.

Ronald Fagin, Jonathan Lenchner, Kenneth W. Regan, Nikhil Vyas

Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 2021

Optimal Fine-Grained Hardness of Approximation of Linear Equations.

Mitali Bafna, Nikhil Vyas

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

Near-Optimal Complexity Bounds for Fragments of the Skolem Problem.

S. Akshay, Nikhil Balaji, Aniket Murhekar, Rohith Varma, Nikhil Vyas

Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse Graphs.

Andrea Lincoln, Nikhil Vyas

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Results on a Super Strong Exponential Time Hypothesis.

Nikhil Vyas, Ryan Williams

Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020

2019

Efficient Constructions for Almost-everywhere Secure Computation.

Siddhartha Jayanti, Srinivasan Raghuraman, Nikhil Vyas

IACR Cryptol. ePrint Arch., 2019

Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems.

Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Approximation Algorithms for Min-Distance Problems.

Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu, Yuancheng Yu

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Imperfect Gaps in Gap-ETH and PCPs.

Mitali Bafna, Nikhil Vyas

Proceedings of the 34th Computational Complexity Conference, 2019

2018

Faster Space-Efficient Algorithms for Subset Sum, k-Sum, and Related Problems.

Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas

SIAM J. Comput., 2018

Thwarting Adversarial Examples: An L₀-RobustSparse Fourier Transform.

Mitali Bafna, Jack Murtagh, Nikhil Vyas

CoRR, 2018

Super Strong ETH is False for Random k-SAT.

Nikhil Vyas

CoRR, 2018

Thwarting Adversarial Examples: An L_0-Robust Sparse Fourier Transform.

Mitali Bafna, Jack Murtagh, Nikhil Vyas

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Distribution-based objectives for Markov Decision Processes.

S. Akshay, Blaise Genest, Nikhil Vyas

Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, 2018

2017

Faster space-efficient algorithms for subset sum and k-sum.

Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Complexity of Restricted Variants of Skolem and Related Problems.

S. Akshay, Nikhil Balaji, Nikhil Vyas

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

2016

On Regularity of Unary Probabilistic Automata.

S. Akshay, Blaise Genest, Bruno Karelovic, Nikhil Vyas

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016