15 citations · 19 across the 7 of their papers we have counts for
12 papers
Baby PIH: Parameterized Inapproximability of Min CSP
Venkatesan Guruswami, Xuandi Ren, Sai Sandeep
The Parameterized Inapproximability Hypothesis (PIH) is the analog of the PCP theorem in the world of parameterized complexity. It asserts that no FPT algorithm can distinguish a s…
Improved Hardness of Approximation for Geometric Bin Packing
Arka Ray, Sai Sandeep
The Geometric Bin Packing (GBP) problem is a generalization of Bin Packing where the input is a set of -dimensional rectangles, and the goal is to pack them into unit -dimens…
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…
On the Hardness of Scheduling With Non-Uniform Communication Delays
Sami Davies, Janardhan Kulkarni, Thomas Rothvoss +3
In the scheduling with non-uniform communication delay problem, the input is a set of jobs with precedence constraints. Associated with every precedence constraint between a pair o…
Conditional Dichotomy of Boolean Ordered Promise CSPs
Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
Promise Constraint Satisfaction Problems (PCSPs) are a generalization of Constraint Satisfaction Problems (CSPs) where each predicate has a strong and a weak form and given a CSP i…
Almost Optimal Inapproximability of Multidimensional Packing Problems
Sai Sandeep
Multidimensional packing problems generalize the classical packing problems such as Bin Packing, Multiprocessor Scheduling by allowing the jobs to be -dimensional vectors. While…