
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.


Publications 


PreReduction Graph
Products: Hardnesses of Properly Learning DFAs and
Approximating EDP on DAGs
P. Chalermsook, B. Laekhanukit and D. Nanongkai
To appear in 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 / To appear in Algorithmica Special Issue for ESA 2012.
(full version)

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 / To appear in ACM Trans. Algorithms.

An improved approximation algorithm for minimumcost subset
kconnectivity,
B. Laekhanukit,
ICALP 2011 / To appear in Algorithmica

Approximation algorithms for minimum cost k(S,T) connected
digraphs,
J. Cheriyan and B. Laekhanukit,
SIAM J. Discrete Math. 273 (2013), pp. 14501481
(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 (2013), pp. 2541

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 (2012), pp. 10951109
 Publications in National Conference in Thailand 



