16 citations · 69 across the 56 of their papers we have counts for
66 papers
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…
Selectivity Estimation for Linear Queries via Online Learning
Fangzhu Shen, Debmalya Panigrahi, Sudeepa Roy
Learning-based approaches for selectivity estimation in databases have gained significant traction in recent years. However, theoretical studies of these learning-based approaches…
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…
A General Framework for Learning-Augmented Online Allocation
Ilan Reuven Cohen, Debmalya Panigrahi
Online allocation is a broad class of problems where items arriving online have to be allocated to agents who have a fixed utility/cost for each assigned item so to maximize/minimi…
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 Algorithms for the Santa Claus Problem
MohammadTaghi Hajiaghayi, MohammadReza Khani, Debmalya Panigrahi +1
The Santa Claus problem is a fundamental problem in fair division: the goal is to partition a set of heterogeneous items among heterogeneous agents so as to maximize the minimum va…
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…
A Regression Approach to Learning-Augmented Online Algorithms
Keerti Anand, Rong Ge, Amit Kumar +1
The emerging field of learning-augmented online algorithms uses ML techniques to predict future input parameters and thereby improve the performance of online algorithms. Since the…