From the 1 of 48 linked papers with an AI index.
1 citations · 1 across the 15 of their papers we have counts for
9 papers · 1 filter
Inapproximability of Unique-Machine Precedence Scheduling for Unit-Length Jobs
Venkatesan Guruswami, Xuandi Ren, Shaoxuan Tang
The paper shows that scheduling unit-length jobs with unique-machine precedence constraints cannot be approximated within any constant factor, and under standard complexity assumpt…
Redundancy Is All You Need (for CSP Sparsification)
Joshua Brakensiek, Venkatesan Guruswami
The seminal work of Benczúr and Karger demonstrated cut sparsifiers of near-linear size. Subsequent extensions have yielded sparsifiers for hypergraph cuts and more recently linea…
New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
Joshua Brakensiek, Lorenzo Ciardo, Venkatesan Guruswami +2
In this paper, we continue the study of robust satisfiability of promise CSPs (PCSPs), initiated in (Brakensiek, Guruswami, Sandeep, STOC 2023 / Discrete Analysis 2025), and obtain…
Tight Bounds for Sparsifying Random CSPs
Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman
The problem of CSP sparsification asks: for a given CSP instance, what is the sparsest possible reweighting such that for every possible assignment to the instance, the number of s…
Scheduling Problems with Constrained Rejections
Sami Davies, Venkatesan Guruswami, Xuandi Ren
We study bicriteria versions of Makespan Minimization on Unrelated Machines and Santa Claus by allowing a constrained number of rejections. Given an instance of Makespan Minimizati…
SDPs and Robust Satisfiability of Promise CSP
Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
For a constraint satisfaction problem (CSP), a robust satisfaction algorithm is one that outputs an assignment satisfying most of the constraints on instances that are near-satisfi…