All reports by Author Sai Sandeep:

__
TR23-155
| 25th October 2023
__

Venkatesan Guruswami, Xuandi Ren, Sai Sandeep#### Baby PIH: Parameterized Inapproximability of Min CSP

Revisions: 1

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 satisfiable 2CSP instance from one which is only $(1-\varepsilon)$-satisfiable (where the parameter is the number of variables) for some constant $0<\varepsilon<1$.

We ... more >>>