Nikhil Vyas

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

Collaborative distances:

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

2024

Distinguishing the Knowable from the Unknowable with Language Models.

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

CoRR, 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

On Privileged and Convergent Bases in Neural Network Representations.

Davis Brown, Nikhil Vyas, Yamini Bansal

CoRR, 2023

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

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

CoRR, 2023

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

Nikhil Vyas, Alexander 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 Oracles and Algorithmic Methods for Proving Lower Bounds.

Nikhil Vyas, Ryan Williams

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 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