Email: lin at nju.edu.cn
PO Box 603, 163 Xianlin Ave, Nanjing, Jiangsu Province, China, 210023
Ph.D. (2016), The University of Tokyo
MS(2013) and BE(2010), ACM Honors Class, Shanghai Jiao Tong University.
Professor, School of Computer Science, Nanjing University.
Research Interests:
graph theory, parameterized complexity, extremal combinatoric, hardness of approximation.
Talk at ITCS, SHUFE. pdf
Talk at ICALP 2019, pdf
Talk at SODA 2020, pdf
Talk at STOC 2021, pdf
Publications:
with Yijia Chen, Yuwei Liu, Shuangle Li, Xin Zheng, On Average Baby PIH and Its Applications. STACS 2025.
with Venkatesan Guruswami, Xuandi Ren, Yican Sun, Kewen Wu, Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH. STOC 2025.
with Venkatesan Guruswami, Xuandi Ren, Yican Sun, Kewen Wu, Parameterized Inapproximability Hypothesis under ETH, STOC 2024, Best Paper Award.(slides)
with Shuangle Li, Yuwei Liu, Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems under ETH, ICALP 2024. (slides)
with Huairui Chu, FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set, ISAAC 2023. (slides)
with Xuandi Ren, Yican Sun, Xiuhan Wang, Improved Hardness of Approximating k-Clique under ETH. FOCS 2023. (slides)
with Xuandi Ren, Yican Sun, Xiuhan Wang, Constant Approximating Parameterized k-SetCover is W[2]-hard. SODA 2023.
with Xuandi Ren, Yican Sun, Xiuhan Wang, On Lower Bounds of Approximating Parameterized k-Clique. ICALP 2022.
with A.Bhattacharyya, É. Bonnet, L. Egri, S. Ghoshal, Karthik C.S., P.Manurangsia, D.Marx, Parameterized Intractability of Even Set and Shortest Vector Problem. Journal of the ACM, 68(3):16:1-16:40, 2021.
with Ken-ichi Kawarabayashi, A nearly 5/3-approximation FPT Algorithm for Min-k-Cut. SODA 2020
A Simple Gap-producing Reduction for the Parameterized Set Cover Problem. ICALP 2019(track A), best paper
The Parameterized Complexity of k-Biclique. Journal of the ACM (JACM), Volume 65 Issue 5 (2018)
Conference version: The Parameterized Complexity of k-Biclique. SODA 2015, best paper and best student paper
with Yijia Chen, The parameterized complexity of k-edge induced subgraphs. Information and Computation, Volume 252 (2017), 138-160
Conference version: The parameterized complexity of k-edge induced subgraphs. ICALP 2012(track A)
with Yijia Chen, The Constant Inapproximability of the Parameterized Dominating Set Problem. FOCS 2016
with Yijia Chen, Martin Grohe, The hardness of embedding grids and walls. WG 2017
with Chihao Zhang, Xiaojie Deng, Multi-Multiway Cut Problem on Graphs of Bounded Branch Width. FAW-AAIM 2013
On Parameterized Inapproximability of Several Optimization Problems. PhD thesis 2016
Links: