38 citations · 157 across the 44 of their papers we have counts for
6 papers · 1 filter
Potential-Function Proofs for First-Order Methods
Nikhil Bansal, Anupam Gupta
This note discusses proofs for convergence of first-order methods based on simple potential-function arguments. We cover methods like gradient descent (for both smooth and non-smoo…
New Tools and Connections for Exponential-time Approximation
Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit +2
In this paper, we develop new tools and connections for exponential time approximation. In this setting, we are given a problem instance and a parameter , and the goal is to d…
The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues
Nikhil Bansal, Daniel Dadush, Shashwat Garg +1
An important result in discrepancy due to Banaszczyk states that for any set of vectors in of norm at most and any convex body in …
Nested Convex Bodies are Chaseable
Nikhil Bansal, Martin Böhm, Marek Eliáš +2
In the Convex Body Chasing problem, we are given an initial point in and an online sequence of convex bodies . When we receive , we are required…
Competitive Algorithms for Generalized k-Server in Uniform Metrics
Nikhil Bansal, Marek Elias, Grigorios Koumoutsos +1
The generalized k-server problem is a far-reaching extension of the k-server problem with several applications. Here, each server lies in its own metric space . A reques…
Weighted k-Server Bounds via Combinatorial Dichotomies
Nikhil Bansal, Marek Elias, Grigorios Koumoutsos
The weighted -server problem is a natural generalization of the -server problem where each server has a different weight. We consider the problem on uniform metrics, which co…