Nikhil Vyas

Publication Activity (10 Years)

Years Active: 2016-2024
Publications (10 Years): 47

Top Topics

Approximation Algorithms

Related Problems

Top Venues

Publications

Mitali Bafna, Dor Minzer, Nikhil Vyas
Quasi-Linear Size PCPs with Small Soundness from HDX. CoRR (2024)
Nikhil Vyas, Ryan Williams
On Oracles and Algorithmic Methods for Proving Lower Bounds. Electron. Colloquium Comput. Complex. (2024)
Depen Morwani, Itai Shapira, Nikhil Vyas, Eran Malach, Sham M. Kakade, Lucas Janson
A New Perspective on Shampoo's Preconditioner. CoRR (2024)
Rosie Zhao, Depen Morwani, David Brandfonbrener, Nikhil Vyas, Sham M. Kakade
Deconstructing What Makes a Good Optimizer for Language Models. CoRR (2024)
Gustaf Ahdritz, Tian Qin, Nikhil Vyas, Boaz Barak, Benjamin L. Edelman
Distinguishing the Knowable from the Unknowable with Language Models. CoRR (2024)
Nikhil Vyas, Ryan Williams
On Oracles and Algorithmic Methods for Proving Lower Bounds. ITCS (2023)
Nikhil Vyas, Sham M. Kakade, Boaz Barak
On Provable Copyright Protection for Generative Models. ICML (2023)
Nikhil Vyas, Depen Morwani, Rosie Zhao, Gal Kaplun, Sham M. Kakade, Boaz Barak
Beyond Implicit Bias: The Insignificance of SGD Noise in Online Learning. CoRR (2023)
Nikhil Vyas, Yamini Bansal, Preetum Nakkiran
Empirical Limitations of the NTK for Understanding Scaling Laws in Deep Learning. Trans. Mach. Learn. Res. 2023 (2023)
Nishanth Dikkala, Nikhil Ghosh, Raghu Meka, Rina Panigrahy, Nikhil Vyas, Xin Wang
On the Benefits of Learning to Route in Mixture-of-Experts Models. EMNLP (2023)
Nikhil Vyas, Alexander Atanasov, Blake Bordelon, Depen Morwani, Sabarish Sainathan, Cengiz Pehlevan
Feature-Learning Networks Are Consistent Across Widths At Realistic Scales. NeurIPS (2023)
Davis Brown, Nikhil Vyas, Yamini Bansal
On Privileged and Convergent Bases in Neural Network Representations. CoRR (2023)
Nikhil Vyas, R. Ryan Williams
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms. Theory Comput. Syst. 67 (1) (2023)
Ronald Fagin, Jonathan Lenchner, Nikhil Vyas, Ryan Williams
On the Number of Quantifiers as a Complexity Measure. CoRR (2022)
Nikhil Vyas, Yamini Bansal, Preetum Nakkiran
Limitations of the NTK for Understanding Generalization in Deep Learning. CoRR (2022)
Ronald Fagin, Jonathan Lenchner, Nikhil Vyas, R. Ryan Williams
On the Number of Quantifiers as a Complexity Measure. MFCS (2022)
Ronald Fagin, Jonathan Lenchner, Kenneth W. Regan, Nikhil Vyas
Multi-Structural Games and Number of Quantifiers. LICS (2021)
Ronald Fagin, Jonathan Lenchner, Kenneth W. Regan, Nikhil Vyas
Multi-Structural Games and Number of Quantifiers. CoRR (2021)
Mitali Bafna, Nikhil Vyas
Optimal Fine-grained Hardness of Approximation of Linear Equations. CoRR (2021)
Nikhil Vyas, R. Ryan Williams
On Super Strong ETH. J. Artif. Intell. Res. 70 (2021)
Ce Jin, Nikhil Vyas, Ryan Williams
Fast Low-Space Algorithms for Subset Sum. SODA (2021)
Mitali Bafna, Nikhil Vyas
Optimal Fine-Grained Hardness of Approximation of Linear Equations. ICALP (2021)
S. Akshay, Nikhil Balaji, Aniket Murhekar, Rohith Varma, Nikhil Vyas
Near-Optimal Complexity Bounds for Fragments of the Skolem Problem. STACS (2020)
Nikhil Vyas, Ryan Williams
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of $\#$SAT Algorithms. CoRR (2020)
Ce Jin, Nikhil Vyas, Ryan Williams
Fast Low-Space Algorithms for Subset Sum. CoRR (2020)
Siddhartha Jayanti, Srinivasan Raghuraman, Nikhil Vyas
Efficient Constructions for Almost-Everywhere Secure Computation. EUROCRYPT (2) (2020)
Andrea Lincoln, Nikhil Vyas
Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse Graphs. ITCS (2020)
Nikhil Vyas, R. Ryan Williams
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms. STACS (2020)
Nikhil Vyas, Ryan Williams
Results on a Super Strong Exponential Time Hypothesis. AAAI (2020)
Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu, Yuancheng Yu
Approximation Algorithms for Min-Distance Problems. ICALP (2019)
Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein
Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems. CoRR (2019)
Nikhil Vyas, R. Ryan Williams
On Super Strong ETH. SAT (2019)
Mitali Bafna, Nikhil Vyas
Imperfect Gaps in Gap-ETH and PCPs. Computational Complexity Conference (2019)
Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu, Yuancheng Yu
Approximation Algorithms for Min-Distance Problems. CoRR (2019)
Siddhartha Jayanti, Srinivasan Raghuraman, Nikhil Vyas
Efficient Constructions for Almost-everywhere Secure Computation. IACR Cryptol. ePrint Arch. 2019 (2019)
Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein
Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems. ICALP (2019)
Mitali Bafna, Nikhil Vyas
Imperfect Gaps in Gap-ETH and PCPs. CoRR (2019)
Nikhil Vyas
Super Strong ETH is False for Random k-SAT. CoRR (2018)
Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas
Faster Space-Efficient Algorithms for Subset Sum, k-Sum, and Related Problems. SIAM J. Comput. 47 (5) (2018)
S. Akshay, Blaise Genest, Nikhil Vyas
Distribution-based objectives for Markov Decision Processes. CoRR (2018)
Mitali Bafna, Jack Murtagh, Nikhil Vyas
-RobustSparse Fourier Transform. CoRR (2018)
S. Akshay, Blaise Genest, Nikhil Vyas
Distribution-based objectives for Markov Decision Processes. LICS (2018)
Mitali Bafna, Jack Murtagh, Nikhil Vyas
Thwarting Adversarial Examples: An L_0-Robust Sparse Fourier Transform. NeurIPS (2018)
S. Akshay, Nikhil Balaji, Nikhil Vyas
Complexity of Restricted Variants of Skolem and Related Problems. MFCS (2017)
Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas
Faster space-efficient algorithms for subset sum and k-sum. STOC (2017)
S. Akshay, Blaise Genest, Bruno Karelovic, Nikhil Vyas
On Regularity of Unary Probabilistic Automata. STACS (2016)
Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas
Faster Space-Efficient Algorithms for Subset Sum, k-Sum and Related Problems. CoRR (2016)