16 citations · 69 across the 56 of their papers we have counts for
55 papers · 1 filter
Online Algorithms with a Sample: Tight Bounds and Adversarial Robustness
Anish Hebbar, Ravi Kumar, Roie Levin +3
Suppose an online algorithm is given an unbiased -sample of its input as offline advice; can the algorithm exploit the sample to achieve beyond-worst-case performance? We study…
Online Metric TSP: Beyond the Barrier
Yossi Azar, Debmalya Panigrahi, Or Vardi
We study an online variant of the Traveling Salesperson Problem (TSP) in which points arrive sequentially and must be inserted into an evolving tour. In the classical setting w…
Hallucination Rates in Language Generation
Debmalya Panigrahi, Fan Wei, Ian Zhang
Language generation in the limit is an elegant model introduced by Kleinberg and Mullainathan [KM24] to formally study language generation by an algorithm that learns solely based…
Stochastic Caching via Subset Entropy
Ravi Kumar, Roie Levin, Joseph +2
A classic approach to beyond worst-case algorithm design is to impose stochastic assumptions on the input. However, a limiting feature of stochastic analyses is that, by the min-ma…
An Optimal Algorithm for Stochastic Vertex Cover
Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju +5
The goal in the stochastic vertex cover problem is to obtain an approximately minimum vertex cover for a graph that is realized by sampling each edge independently with s…
Learning-Augmented Algorithms for -median via Online Learning
Anish Hebbar, Rong Ge, Amit Kumar +1
The field of learning-augmented algorithms seeks to use ML techniques on past instances of a problem to inform an algorithm designed for a future instance. In this paper, we introd…
Complexity of Local Search for CSPs Parameterized by Constraint Difference
Aditya Anand, Vincent Cohen-Addad, Tommaso d'Orsi +4
In this paper, we study the parameterized complexity of local search, whose goal is to find a good nearby solution from the given current solution. Formally, given an optimization…
Fully Dynamic Set Cover: Worst-Case Recourse and Update Time
Sayan Bhattacharya, Ruoxu Cen, Debmalya Panigrahi
In (fully) dynamic set cover, the goal is to maintain an approximately optimal solution to a dynamically evolving instance of set cover, where in each step either an element is add…
Combinatorial Optimization using Comparison Oracles
Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta +7
In linear combinatorial optimization, we aim to find for a family over a ground set…
Nearly Tight Bounds for the Online Sorting Problem
Yossi Azar, Debmalya Panigrahi, Or Vardi
In the online sorting problem, a sequence of numbers in (including ) have to be inserted in an array of size so as to minimize the sum of absolute d…
Deterministic Almost-Linear-Time Gomory-Hu Trees
Amir Abboud, Rasmus Kyng, Jason Li +5
Given an -edge, undirected, weighted graph , a Gomory-Hu tree (Gomory and Hu, 1961) is a tree over the vertex set such that all-pairs mincuts in are prese…
Fast Algorithms for Graph Arboricity and Related Problems
Ruoxu Cen, Henry Fleischmann, George Z. Li +2
We give an algorithm for finding the arboricity of a weighted, undirected graph, defined as the minimum number of spanning forests that cover all edges of the graph, in $\sqrt{n} m…
Language Generation in the Limit: Noise, Loss, and Feedback
Yannan Bai, Debmalya Panigrahi, Ian Zhang
Kleinberg and Mullainathan (2024) recently proposed a formal framework called language generation in the limit and showed that given a sequence of example strings from an unknown t…
Network Unreliability in Almost-Linear Time
Ruoxu Cen, Jason Li, Debmalya Panigrahi
The network unreliability problem asks for the probability that a given undirected graph gets disconnected when every edge independently fails with a given probability . Valiant…
Hypergraph Unreliability in Quasi-Polynomial Time
Ruoxu Cen, Jason Li, Debmalya Panigrahi
The hypergraph unreliability problem asks for the probability that a hypergraph gets disconnected when every hyperedge fails independently with a given probability. For graphs, the…
Max-Cut with -Accurate Predictions
Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta +2
We study the approximability of the MaxCut problem in the presence of predictions. Specifically, we consider two models: in the noisy predictions model, for each vertex we are give…
Efficient Algorithms and Hardness Results for the Weighted -Server Problem
Anupam Gupta, Amit Kumar, Debmalya Panigrahi
In this paper, we study the weighted -server problem on the uniform metric in both the offline and online settings. We start with the offline setting. In contrast to the (unweig…
Beyond the Quadratic Time Barrier for Network Unreliability
Ruoxu Cen, William He, Jason Li +1
Karger (STOC 1995) gave the first FPTAS for the network (un)reliability problem, setting in motion research over the next three decades that obtained increasingly faster running ti…
Steiner Connectivity Augmentation and Splitting-off in Poly-logarithmic Maximum Flows
Ruoxu Cen, William He, Jason Li +1
We give an almost-linear time algorithm for the Steiner connectivity augmentation problem: given an undirected graph, find a smallest (or minimum weight) set of edges whose additio…
Online Paging with Heterogeneous Cache Slots
Marek Chrobak, Samuel Haney, Mehraneh Liaee +4
It is natural to generalize the online -Server problem by allowing each request to specify not only a point , but also a subset of servers that may serve it. For uniform…
Edge Connectivity Augmentation in Near-Linear Time
Ruoxu Cen, Jason Li, Debmalya Panigrahi
We give an -time algorithm for the edge connectivity augmentation problem and the closely related edge splitting-off problem. This is optimal up to lower order terms…
Near-Linear Time Approximations for Cut Problems via Fair Cuts
Jason Li, Danupon Nanongkai, Debmalya Panigrahi +1
We introduce the notion of {\em fair cuts} as an approach to leverage approximate -mincut (equivalently -maxflow) algorithms in undirected graphs to obtain near-linea…
Online Graph Algorithms with Predictions
Yossi Azar, Debmalya Panigrahi, Noam Touitou
Online algorithms with predictions is a popular and elegant framework for bypassing pessimistic lower bounds in competitive analysis. In this model, online algorithms are supplied…
A Hitting Set Relaxation for -Server and an Extension to Time-Windows
Anupam Gupta, Amit Kumar, Debmalya Panigrahi
We study the -server problem with time-windows. In this problem, each request arrives at some point of an -point metric space at time and comes with a deadlin…