2 citations · 3 across the 14 of their papers we have counts for
3 papers · 1 filter
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…
PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs
Venkatesan Guruswami, Xuandi Ren, Kewen Wu
The Reconfiguration Inapproximability Hypothesis (RIH), recently established by Hirahara-Ohsaka (STOC'24) and Karthik-Manurangsi (ECCC'24), studies the hardness of reconfiguring on…
PCP-free APX-Hardness of Nearest Codeword and Minimum Distance
Vijay Bhattiprolu, Venkatesan Guruswami, Xuandi Ren
We give simple deterministic reductions demonstrating the NP-hardness of approximating the nearest codeword problem and minimum distance problem within arbitrary constant factors (…