Nikhil Vyas
nikhilv at mit.edu
vyasnikhil96 at gmail.com
I am a graduate student in theoretical computer science at MIT where I am advised by Ryan Williams.
Before grad school, I did my undergrad in computer science at IIT Bombay.
Publications
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
Thwarting Adversarial Examples: An L_0-Robust Sparse Fourier Transform.
Mitali Bafna, Jack Murtagh, Nikhil Vyas
NeurIPS 2018
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
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.