2 citations · 3 across the 14 of their papers we have counts for
4 papers · 1 filter
On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
Venkatesan Guruswami, Karthik C. S., Pasin Manurangsi +2
Recently, Ohsaka [STACS'23] put forth the Reconfiguration Inapproximability Hypothesis (RIH), which roughly asserts that there is some such that given as input a -CSP inst…
Parameterized Inapproximability Hypothesis under ETH
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren +2
The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the numb…
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 Approximating k-Clique under ETH
Bingkai Lin, Xuandi Ren, Yican Sun +1
In this paper, we prove that assuming the exponential time hypothesis (ETH), there is no -time algorithm that can decide whether an -vertex gr…