38 citations · 157 across the 44 of their papers we have counts for
6 papers · 1 filter
Learning-Augmented Weighted Paging
Nikhil Bansal, Christian Coester, Ravi Kumar +2
We consider a natural semi-online model for weighted paging, where at any time the algorithm is given predictions, possibly with errors, about the next arrival of each page. The mo…
Some remarks on hypergraph matching and the Füredi-Kahn-Seymour conjecture
Nikhil Bansal, David G. Harris
A classic conjecture of Füredi, Kahn and Seymour (1993) states that given any hypergraph with non-negative edge weights , there exists a matching such that $\sum_{e \in M…
An Asymptotic Lower Bound for Online Vector Bin Packing
Nikhil Bansal, Ilan Reuven Cohen
We consider the online vector bin packing problem where items specified by -dimensional vectors must be packed in the fewest number of identical -dimensional bins. Azar e…
-Forrelation Optimally Separates Quantum and Classical Query Complexity
Nikhil Bansal, Makrand Sinha
Aaronson and Ambainis (SICOMP `18) showed that any partial function on bits that can be computed with an advantage over a random guess by making quantum queries, can al…
Online Discrepancy Minimization for Stochastic Arrivals
Nikhil Bansal, Haotian Jiang, Raghu Meka +2
In the stochastic online vector balancing problem, vectors chosen independently from an arbitrary distribution in arrive one-by-one and must be…
Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover
Nikhil Bansal, Jatin Batra, Majid Farhadi +1
We study the generalized min sum set cover (GMSSC) problem, wherein given a collection of hyperedges with arbitrary covering requirements , the goal is to find an ordering…