All reports by Author Xuandi Ren:

__
TR24-075
| 13th April 2024
__

Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu#### Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH

__
TR23-188
| 28th November 2023
__

Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu#### Parameterized Inapproximability Hypothesis under ETH

__
TR23-155
| 25th October 2023
__

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

Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu

The Parameterized Inapproximability Hypothesis (PIH), which is an analog of the PCP theorem in parameterized complexity, asserts that, there is a constant $\varepsilon> 0$ such that for any computable function $f:\mathbb{N}\to\mathbb{N}$, no $f(k)\cdot n^{O(1)}$-time algorithm can, on input a $k$-variable CSP instance with domain size $n$, find an assignment satisfying ... more >>>

Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu

The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the number of variables, from one where every assignment fails to satisfy an $\varepsilon$ fraction of constraints for some absolute constant $\varepsilon > 0$. PIH plays the role of ... more >>>

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 >>>