Assistant professor
Department of Computer Science, 
Aalto University 

ERC Starting Grant, 2018 - 2022

My broad area of research interests is in theoretical computer science. More specifically, I study various aspects of efficient computations: approximation algorithms, hardness of approximation, data structures, and online algorithms. I completed my PhD from the department of computer science, University of Chicago in 2012, under the supervision of Julia Chuzhoy (at TTI-C) and Janos Simon

After my Ph.D, I did a short (and yet very pleasant) postdoc at IDSIA. Afterwards, I spent 3.5 years rising from a postdoc to a senior researcher at Max Planck Institute for Informatics

  • [August 2017] My research in the next 5 years will also be supported by ERC Starting Grant. The total amount is ~1.4M Euro. I will be looking for researchers at all levels (postdocs/doctoral/master) to join the team. If you think your research interest has overlap with mine and want to pursue some challenges together, please drop an e-mail. 

  • [July 2017] Our paper "From Gap-ETH to FPT Inapproximability: Clique, Dominating Set and More" has been accepted to FOCS 2017. 
  • [May 2017] I received the funding from Academy of Finland (Aof) under the Academy Research Fellow (total~900K EUR) funding scheme. The funding will run from September 2017 to August 2022.
  • I will spend the Fall 2017 semester at Simons Institute on Theory of Computing, Berkeley. 

Representative papers
Here is a list of what I view as my "most interesting" publications. For the full list of publications, please refer to the publication page.
  1. Pattern Avoiding Access in Binary Search Trees. [PDF]
    P. Chalermsook, M. Goswami, L. Kozma, K. Mehlhorn, and T. Saranurak. 
    FOCS 2015 &  
    HALG 2016 (contributed paper)

  2. Pre-Reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs. [PDF]
    P. Chalermsook, B. Laekhanukit, D. Nanongkai 
    FOCS 2014

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

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

  5. Approximation Algorithms and Hardness of Integral Concurrent Flow. [PDF]
    P. Chalermsook, J. Chuzhoy, A. Ene, S. Li. 
    STOC 2012.

  6. Maximum Independent Set of Rectangles. [PDF]
    P. Chalermsook, J. Chuzhoy. 
    SODA 2009.

Professional Services
  • PC Member
    • International Symposium on Algorithms and Computation (ISAAC 2017
    • European Symposium on Algorithms (ESA 2016
    • Fun with Algorithms (FUN 2016)
    • Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
    • International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2015

  • Organizer
    • European Symposium on Algorithms (ESA) 2018. With Petteri Kaski and Jukka Suomela. 
    • Max Planck Advanced Course on Foundations of Computer Science (ADFOCS) 2014. With A. Karrenbauer. 

Konemiehentie 2, Espoo/Otaniemi, 
02150, Finland
Room B305

Aalto e-mail always follows the format