
Education 
 B.Eng (Computer Engineering)
Kasetsart University, Bangkok, Thailand
 M.Eng (Computer Engineering)
Kasetsart University, Bangkok, Thailand
(under supervision of J. Fakcharoenphol)
M.Eng Thesis:
Faster algorithms for optimal semimatching problems.
(originally written in Thai, conference version
in ICALP 2010).
 M.Math (Combinatorics and Optimization)
University of Waterloo, Waterloo ON, Canada
(under supervision of J. Cheriyan)
M.Math Thesis:
Approximation algorithms for (S,T)connectivity problems.
 Ph.D. (Computer Science)
McGill University, Montreal QC, Canada
(under supervision of A. Vetta)
Ph.D. Thesis:
Inapproximability of Combinatorial Problems in
SubexponentialTime.


Preprints 



Publications 


On the Parameterized Complexity of
Approximating Dominating Set
Karthik C. S., B.Laekhanukit and P. Manurangsi
To appear in STOC 2018. Invited to SICOMP special issue for STOC 2018 (regretfully declined).

On the Complexity
of Closest Pair via PolarPair of PointSets
R. David, Karthik C. S. and B. Laekhanukit
To appear in SoCG 2018.

From GapETH to FPTInapproximability: Clique, Dominating Set, and More
P. Chalermsook, M. Cygan, G. Kortsarz, B.Laekhanukit, P. Manurangsi, D. Nanongkai and L. Trevisan
FOCS 2017.

Surviving in Directed Graphs:
A QuasiPolynomialTime Polylogarithmic Approximation for
TwoConnected Directed Steiner Tree
F. Grandoni and B. Laekhanukit
STOC 2017.

Beyond Metric Embedding: Approximating
Group Steiner Trees on Bounded Treewidth Graphs
P. Chalermsook, S. Das, B. Laekhanukit and D. Vaz
SODA 2017.

Approximating Spanners and Directed
Steiner Forest: Upper and Lower Bounds
E. Chlamtac, M. Dinitz, G. Kortsarz and B. Laekhanukit
SODA 2017.

Approximating Directed Steiner
Problems via Tree Embedding
B. Laekhanukit
ICALP 2016.

On Survivable Set Connectivity
P. Chalermsook, F. Grandoni and B. Laekhanukit
SODA 2015.

PreReduction Graph
Products: Hardnesses of Properly Learning DFAs and
Approximating EDP on DAGs
P. Chalermsook, B. Laekhanukit and D. Nanongkai
FOCS 2014.

Coloring Graph Powers:
Graph Product Bounds and Hardness of Approximation
P. Chalermsook, B. Laekhanukit and D. Nanongkai
LATIN 2014.

Parameters of
TwoProverOneRound Game and The Hardness of Connectivity
Problems
SODA 2014.

Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses
P. Chalermsook, B. Laekhanukit and D. Nanongkai
FOCS 2013.

Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension, and More,
P. Chalermsook, B. Laekhanukit and D. Nanongkai
SODA 2013

NonRedistributive Second Welfare Theorems,
B. Laekhanukit, G. Naves and A. Vetta
WINE 2012

Routing Regardless of Network Stability,
B. Laekhanukit, A. Vetta and G. Wilfong
ESA 2012 / Algorithmica 70(3): 561593 (2014) (ESA special issue).

A rounding by sampling approach to the minimum size karc
connected subgraph problem,
B. Laekhanukit, S. Oveis Gharan and M. Singh
ICALP 2012.

Approximating rooted Steiner networks,
J. Cheriyan, B. Laekhanukit, G. Naves and A. Vetta
SODA 2012 / ACM Transactions on Algorithms 11(2): 8 (2014).

An improved approximation algorithm for minimumcost subset
kconnectivity,
B. Laekhanukit,
ICALP 2011 / Algorithmica 72(3): 714733 (2015).

Approximation algorithms for minimum cost k(S,T) connected
digraphs,
J. Cheriyan and B. Laekhanukit,
SIAM J. Discrete Math. 273: 14501481 (2013)
(preliminary version in
M.Math Thesis)

A bad example for the iterative rounding method for mincost
kconnected spanning subgraphs,
A. Aazami, J. Cheriyan and B. Laekhanukit,
Discrete Optimization 101: 2541 (2013)

Improved hardness of approximation for Stackelberg shortestpath
pricing,
P. Briest, P. Chalermsook, S.Khanna, B. Laekhanukit
and D. Nanongkai,
WINE 2010 (short paper).
(Preliminary versions in
[arXiv]
and
[arXiv])

Faster algorithms for semimatching problems,
J. Fakcharoenphol, B. Laekhanukit and D. Nanongkai,
ICALP 2010 / ACM Trans. Algorithms 10(3): 14 (2014).
(Preliminary versions in
[arXiv])

An O(log^{2} k)approximation algorithm for the kvertex
connected spanning subgraph problem,
J. Fakcharoenphol and B. Laekhanukit,
STOC 2008 / SIAM J. Comput. 415: 10951109 (2012)
 Publications in National Conference in Thailand 



