6 citations · 20 across the 18 of their papers we have counts for
23 papers
Better Late Than Never: Online Flow Time Scheduling with Online Estimates
Anupam Gupta, Haim Kaplan, Alexander Lindermayr +2
In the classical online flow-time scheduling problem on a single machine, jobs arrive over time and must be processed to minimize the total time they spend in the system: for over…
A Simpler Analysis for -Clairvoyant Flow Time Scheduling
Anupam Gupta, Haim Kaplan, Alexander Lindermayr +2
We simplify the proof of the optimality of the Shortest Lower-Bound First (SLF) algorithm, introduced by Gupta, Kaplan, Lindermayr, Schlöter, and Yingchareonthawornchai [FOCS'25],…
CSLib: The Lean Computer Science Library
Clark Barrett, Swarat Chaudhuri, Fabrizio Montesi +5
We introduce CSLib, an open-source framework for proving computer-science-related theorems and writing formally verified code in the Lean proof assistant. CSLib aims to be for comp…
A Little Clairvoyance Is All You Need
Anupam Gupta, Haim Kaplan, Alexander Lindermayr +2
We revisit the classical problem of minimizing the total flow time of jobs on a single machine in the online setting where jobs arrive over time. It has long been known that the Sh…
Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
Olivier Fischer, Yonggang Jiang, Sagnik Mukhopadhyay +1
Vertex connectivity and its variants are among the most fundamental problems in graph theory, with decades of extensive study and numerous algorithmic advances. The directed varian…
Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
Yonggang Jiang, Chaitanya Nalam, Thatchaphol Saranurak +1
We give a deterministic algorithm for computing a global minimum vertex cut in a vertex-weighted graph vertices and edges in time. This breaks the long-sta…