All reports by Author Bingkai Lin:

__
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

__
TR19-115
| 4th September 2019
__

Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx#### Parameterized Intractability of Even Set and Shortest Vector Problem

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

Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx

The k-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over $\mathbb{F}_2$, which can be stated as follows: given a generator matrix A and an integer k, determine whether the code generated by A has distance at most k, or in other words, whether ... more >>>