21 citations · 33 across the 9 of their papers we have counts for
6 papers · 1 filter
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…
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…
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…
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…
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…