15 citations · 19 across the 7 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2023
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…
cs.CC2021★ 15 cited
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…