Bingkai Lin
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Bingkai Lin has a total of 7 co-authors. Here are the top co-authors by number of shared publications:
- Venkatesan Guruswami
University of California at Berkeley, Berkeley, USA
3 shared publications - Xuandi Ren
UC Berkeley, Berkeley, CA, USA
3 shared publications - Yican Sun
Peking University
3 shared publications - Kewen Wu
University of California, Berkeley, USA
2 shared publications - Kewen Wu
University of California at Berkeley, Berkeley, USA
1 shared publication Yijia Chen
1 shared publication
Latest Publications
- Open Access
- 9 October 2025
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 72 (5) , 1-40
Parameterized Inapproximability Hypothesis under ETH
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 ɛ fraction of constraints for some absolute constant ɛ > 0. PIH plays the role of the PCP theorem in parameterized complexity. However, PIH has only been established under the Gap Exponential Time Hypothesis (ETH), a very strong assumption with an inherent gap. In this work, we prove PIH under the ETH. This is the first proof of PIH from a gap-free assumption. Our proof is self-contained and elementary. We identify an ETH-hard CSP whose variables take vector values, and constraints are either linear or of a special parallel structure. Both kinds of constraints can be checked with constant soundness via a “parallel PCP of proximity” based on the Walsh-Hadamard code.
- 9 October 2025
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 72 (5) , 1-40
Open AccessParameterized Inapproximability Hypothesis under ETH
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 ɛ fraction of constraints for some absolute constant ɛ > 0. PIH plays the role of the PCP theorem in parameterized complexity. However, PIH has only been established under the Gap Exponential Time Hypothesis (ETH), a very strong assumption with an inherent gap. In this work, we prove PIH under the ETH. This is the first proof of PIH from a gap-free assumption. Our proof is self-contained and elementary. We identify an ETH-hard CSP whose variables take vector values, and constraints are either linear or of a special parallel structure. Both kinds of constraints can be checked with constant soundness via a “parallel PCP of proximity” based on the Walsh-Hadamard code.
- 5 October 2025
- Published by Elsevier in Computer Science Review
- Vol. 59
Parameterized inapproximability: From Clique to PIH
- 5 October 2025
- Published by Elsevier in Computer Science Review
- Vol. 59
Parameterized inapproximability: From Clique to PIH
- Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 2136-2144
Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 2136-2144
Open AccessAlmost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
- Open Access
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 24-35
Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis
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 ε fraction of constraints for some absolute constant ε > 0. PIH plays the role of the PCP theorem in parameterized complexity. However, PIH has only been established under Gap-ETH, a very strong assumption with an inherent gap. In this work, we prove PIH under the Exponential Time Hypothesis (ETH). This is the first proof of PIH from a gap-free assumption. Our proof is self-contained and elementary. We identify an ETH-hard CSP whose variables take vector values, and constraints are either linear or of a special parallel structure. Both kinds of constraints can be checked with constant soundness via a “parallel PCP of proximity” based on the Walsh-Hadamard code.
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 24-35
Open AccessParameterized Inapproximability Hypothesis under Exponential Time Hypothesis
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 ε fraction of constraints for some absolute constant ε > 0. PIH plays the role of the PCP theorem in parameterized complexity. However, PIH has only been established under Gap-ETH, a very strong assumption with an inherent gap. In this work, we prove PIH under the Exponential Time Hypothesis (ETH). This is the first proof of PIH from a gap-free assumption. Our proof is self-contained and elementary. We identify an ETH-hard CSP whose variables take vector values, and constraints are either linear or of a special parallel structure. Both kinds of constraints can be checked with constant soundness via a “parallel PCP of proximity” based on the Walsh-Hadamard code.
- Open Access
- 15 June 2021
- Published by Association for Computing Machinery (ACM)
- p. 1749-1756
Constant approximating k-clique is w[1]-hard
For every graph G, let ω(G) be the largest size of complete subgraph in G. This paper presents a simple algorithm which, on input a graph G, a positive integer k and a small constant є>0, outputs a graph G′ and an integer k′ in 2Θ(k5)· |G|O(1)-time such that (1) k′≤ 2Θ(k5), (2) if ω(G)≥ k, then ω(G′)≥ k′, (3) if ω(G)<k, then ω(G′)< (1−є)k′. This implies that no f(k)· |G|O(1)-time algorithm can distinguish between the cases ω(G)≥ k and ω(G)<k/c for any constant c≥ 1 and computable function f, unless FPT= W[1].
- 15 June 2021
- Published by Association for Computing Machinery (ACM)
- p. 1749-1756
Open AccessConstant approximating k-clique is w[1]-hard
For every graph G, let ω(G) be the largest size of complete subgraph in G. This paper presents a simple algorithm which, on input a graph G, a positive integer k and a small constant є>0, outputs a graph G′ and an integer k′ in 2Θ(k5)· |G|O(1)-time such that (1) k′≤ 2Θ(k5), (2) if ω(G)≥ k, then ω(G′)≥ k′, (3) if ω(G)<k, then ω(G′)< (1−є)k′. This implies that no f(k)· |G|O(1)-time algorithm can distinguish between the cases ω(G)≥ k and ω(G)<k/c for any constant c≥ 1 and computable function f, unless FPT= W[1].
- 1 February 2017
- Published by Elsevier in Information and Computation
- Vol. 252, 138-160
The parameterized complexity of k-edge induced subgraphs
- 1 February 2017
- Published by Elsevier in Information and Computation
- Vol. 252, 138-160
The parameterized complexity of k-edge induced subgraphs