21 citations · 33 across the 9 of their papers we have counts for
13 papers
On Provable Copyright Protection for Generative Models
Nikhil Vyas, Sham Kakade, Boaz Barak
There is a growing concern that learned conditional generative models may output samples that are substantially similar to some copyrighted data that was in their training set.…
On the Number of Quantifiers as a Complexity Measure
Ronald Fagin, Jonathan Lenchner, Nikhil Vyas +1
In 1981, Neil Immerman described a two-player game, which he called the "separability game" \cite{Immerman81}, that captures the number of quantifiers needed to describe a property…
Optimal Fine-grained Hardness of Approximation of Linear Equations
Mitali Bafna, Nikhil Vyas
The problem of solving linear systems is one of the most fundamental problems in computer science, where given a satisfiable linear system , for $A \in \mathbb{R}^{n \times…
Multi-Structural Games and Number of Quantifiers
Ronald Fagin, Jonathan Lenchner, Kenneth W. Regan +1
We study multi-structural games, played on two sets and of structures. These games generalize Ehrenfeucht-Fraïssé games. Whereas Ehrenfeucht-Fraïssé gam…
Fast Low-Space Algorithms for Subset Sum
Ce Jin, Nikhil Vyas, Ryan Williams
We consider the canonical Subset Sum problem: given a list of positive integers and a target integer with for all , determine if there is an $S \s…
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of SAT Algorithms
Nikhil Vyas, Ryan Williams
We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in…
Imperfect Gaps in Gap-ETH and PCPs
Mitali Bafna, Nikhil Vyas
We study the role of perfect completeness in probabilistically checkable proof systems (PCPs) and give a new way to transform a PCP with imperfect completeness to a PCP with perfec…
Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas +1
Some of the most fundamental and well-studied graph parameters are the Diameter (the largest shortest paths distance) and Radius (the smallest distance for which a "center" node ca…
Approximation Algorithms for Min-Distance Problems
Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas +3
We study fundamental graph parameters such as the Diameter and Radius in directed graphs, when distances are measured using a somewhat unorthodox but natural measure: the distance…
Thwarting Adversarial Examples: An -RobustSparse Fourier Transform
Mitali Bafna, Jack Murtagh, Nikhil Vyas
We give a new algorithm for approximating the Discrete Fourier transform of an approximately sparse signal that has been corrupted by worst-case noise, namely a bounded numbe…
Super Strong ETH is False for Random -SAT
Nikhil Vyas
It has been hypothesized that -SAT is hard to solve for randomly chosen instances near the "critical threshold", where the clause-to-variable ratio is . Feige's…
Distribution-based objectives for Markov Decision Processes
S. Akshay, Blaise Genest, Nikhil Vyas
We consider distribution-based objectives for Markov Decision Processes (MDP). This class of objectives gives rise to an interesting trade-off between full and partial information.…
Faster Space-Efficient Algorithms for Subset Sum, k-Sum and Related Problems
Nikhil Bansal, Shashwat Garg, Jesper Nederlof +1
We present space efficient Monte Carlo algorithms that solve Subset Sum and Knapsack instances with items using time and polynomial space, where the $O^*(\cdot…