Home
Home
Lin
Bingkai (林 冰凱)
Email: lin at nii.ac.jp
National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan
Ph.D. 2016, The University of Tokyo
Curriculum Vitae
I am
a
Postdoctoral Researcher at the
National Institute of Informatics
,
part of the
JST, ERATO,
Kawarabayashi Large Graph Project
.
Research Interests:
graph theory, parameterized complexity, extremal combinatoric, hardness of
approximation in
fixed-parameter time.
Talk at
ITCS, SHUFE
.
pdf
Talk at FOCS 2016,
pdf
Talk at PAAW,
pdf
Publications:
with
Yijia Chen
,
The parameterized complexity of k-edge induced subgraphs
.
ICALP 2012(track A)
with
Chihao Zhang
,
Xiaojie Deng
,
Multi-Multiway Cut Problem on Graphs of Bounded Branch Width
.
FAW-AAIM 2013
The Parameterized Complexity of k-Biclique
.
SODA 2015
,
best paper and best student paper
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
A Simple Gap-producing Reduction for the Parameterized Set Cover Problem.
Manuscript.
with
Édouard Bonnet
,
László Egri,
Dániel Marx
,
Fixed-parameter Approximability of Boolean MinCSPs
.
On Parameterized Inapproximability of Several Optimization Problems
. PhD thesis 2016
Links:
School on Parameterized Algorithms and Complexity
Open Problem List
Parameterized Complexity Wiki
Ten
Lessons I wish I had been Taught
The Barrier of Meaning(an interesting discussion on the AI-problem)
Graph Classes