Tuukka Korhonen

I am a first-year computer science PhD student at University of Bergen supervised by Fedor V. Fomin. I got my master's degree at University of Helsinki, where I did research in the Constraint Reasoning and Optimization group.

My current research interests are parameterized algorithms and complexity, in particular topics related to tree decompositions.

Research

Publications

• A Single-Exponential Time 2-Approximation Algorithm for Treewidth. Tuukka Korhonen. FOCS 2021.
• Integrating Tree Decompositions into Decision Heuristics of Propositional Model Counters. Tuukka Korhonen and Matti Järvisalo. CP 2021.
• Lower Bounds on Dynamic Programming for Maximum Weight Independent Set. Tuukka Korhonen. ICALP 2021. Arxiv version.
• Finding Optimal Triangulations Parameterized by Edge Clique Cover. Tuukka Korhonen. IPEC 2020 (Best Paper Award). Arxiv version. To appear in Algorithmica special issue for IPEC 2020.
• PACE solver description: SMS. Tuukka Korhonen. IPEC 2020. Arxiv version.
• Finding Most Compatible Phylogenetic Trees over Multi-State Characters. Tuukka Korhonen and Matti Järvisalo. AAAI 2020.
• Enumerating Potential Maximal Cliques via SAT and ASP. Tuukka Korhonen, Jeremias Berg and Matti Järvisalo. IJCAI 2019.
• Solving Graph Problems via Potential Maximal Cliques: An Experimental Evaluation of the Bouchitté-Todinca Algorithm. Tuukka Korhonen, Jeremias Berg and Matti Järvisalo. ACM Journal of Experimental Algorithmics, Volume 24 Issue 1, 2019.
• MaxPre: An Extended MaxSAT Preprocessor. Tuukka Korhonen, Jeremias Berg, Paul Saikko and Matti Järvisalo. SAT 2017.

Preprints and manuscripts

• Fast FPT-Approximation of Branchwidth. Fedor V. Fomin and Tuukka Korhonen. 2021.
• Listing Small Minimal Separators of a Graph. Tuukka Korhonen. 2020.
• Tight Bounds for Potential Maximal Cliques Parameterized by Vertex Cover. Tuukka Korhonen. 2020.

Talks

• Fast FPT-Approximation of Branchwidth. (slides, video) at Workshop on Parametrized complexity and discrete optimization at Hausdorff Research Institute for Mathematics, December 2021.
• Fast FPT-Approximation of Branchwidth. (slides) at IBS Virtual Discrete Math Colloquium, November 2021.
• Integrating Tree Decompositions into Decision Heuristics of Propositional Model Counters. (slides, video) at CP 2021.
• Lower Bounds on Dynamic Programming for Maximum Weight Independent Set. (slides, video) at ICALP 2021.
• SharpSAT-TD: Improving SharpSAT by Exploiting Tree Decompositions. (slides, video) at Workshop on Model Counting 2021.
• A Single-Exponential Time 2-Approximation Algorithm for Treewidth. (slides, video) at Frontiers of Parameterized Complexity online seminar, May 2021.
• Finding Optimal Triangulations Parameterized by Edge Clique Cover. (slides, video) at IPEC 2020.
• PACE solver description: SMS. (slides) at IPEC 2020.
• Finding Most Compatible Phylogenetic Trees over Multi-State Characters. (slides, poster) at AAAI 2020.
• Enumerating Potential Maximal Cliques via SAT and ASP. (slides, poster) at IJCAI 2019.

MSc thesis

• Finding Optimal Tree Decompositions. MSc thesis, University of Helsinki, 2020.

Software

• SharpSAT-TD - #SAT-solver that utilizes tree decompositions.
• SMS - Exact algorithm for computing treedepth using small minimal separators.
• Triangulator - Implementation of the Bouchitté-Todinca algorithm for exact computing of optimal triangulations with various notions of "optimal".
• MaxPre - MaxSAT preprocessor.

Awards

• VCLA International Student Awards 2021 Outstanding Master Thesis Award
• Finnish Society for Computer Science Master's thesis award - the best computer science Master's thesis in Finland in the academic year 2019-2020
• IPEC 2020 Best Paper Award and Best Student Paper Award

Competitions

• 1st place in Model Counting Competition 2021, tracks 1, 2, and 4.
• 2nd place in PACE 2020, exact treedepth track.
• 2nd place in PACE 2017, exact minimum fill-in track.

Reviewing

• Conferences: AAAI 2022, SAT 2021, ICALP 2021, AAAI 2021, MFCS 2020, SAT 2020
• Journals: Theoretical Computer Science

Other

Education

• Currently PhD student at University of Bergen, started in 9/2021.
• Master of Science, Computer Science, University of Helsinki, 7/2020.
• Bachelor of Science, Computer Science, University of Helsinki, 9/2019.

Experience

• 8/2020-7/2021. Mandatory (non)-military service as research assistant at University of Helsinki.
• 6/2016-6/2017, 10/2017-5/2018, 2/2019-7/2020. Research assistant in Constraint Reasoning and Optimization group at University of Helsinki.
• 6/2018-12/2018. Software engineering intern at Google Zürich.
• 7/2017-9/2017. Software developer intern at Jane Street London.

Programming contests

• My profiles at online programming contest sites: Codeforces, Topcoder, Atcoder.
• Results in ICPC: 13th in finals 2017, 14th in finals 2016, 2nd in NWERC 2016, 1st in NWERC 2015, 1st in NCPC 2016, 2nd in NCPC 2015.
• Results in high school contests: bronze medal in IOI 2015, silver medal in BOI 2015, first place in Finnish olympiad in informatics 2015.