16 citations · 69 across the 56 of their papers we have counts for
8 papers · 1 filter
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…