# 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.