Tuukka Korhonen
I am a second-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
- An Improved Parameterized Algorithm for Treewidth. with Daniel Lokshtanov. STOC 2023.
- Grid Induced Minor Theorem for Graphs of Small Degree. Journal of Combinatorial Theory, Series B, 160:206-214, 2023.
- Tight Lower Bounds for Problems Parameterized by Rank-width. with Benjamin Bergougnoux and Jesper Nederlof. STACS 2023.
- Shortest Cycles With Monotone Submodular Costs. with Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Giannos Stamoulis. SODA 2023.
- Fixed-Parameter Tractability of Maximum Colored Path and Beyond. with Fedor V. Fomin, Petr A. Golovach, Kirill Simonov, and Giannos Stamoulis. SODA 2023.
- Fast FPT-Approximation of Branchwidth. with Fedor V. Fomin. STOC 2022.
- A Single-Exponential Time 2-Approximation Algorithm for Treewidth. FOCS 2021.
- Integrating Tree Decompositions into Decision Heuristics of Propositional Model Counters. with Matti Järvisalo. CP 2021.
- Lower Bounds on Dynamic Programming for Maximum Weight Independent Set. ICALP 2021.
- Finding Optimal Triangulations Parameterized by Edge Clique Cover. IPEC 2020 (Best Paper Award). Algorithmica, 84:2242-2270, 2022, special issue for IPEC 2020.
- PACE solver description: SMS. IPEC 2020.
- Finding Most Compatible Phylogenetic Trees over Multi-State Characters. with Matti Järvisalo. AAAI 2020.
- Enumerating Potential Maximal Cliques via SAT and ASP. with Jeremias Berg and Matti Järvisalo. IJCAI 2019.
- Solving Graph Problems via Potential Maximal Cliques: An Experimental Evaluation of the Bouchitté-Todinca Algorithm. with Jeremias Berg and Matti Järvisalo. ACM Journal of Experimental Algorithmics, 24:1.9, 2019.
- MaxPre: An Extended MaxSAT Preprocessor. with Jeremias Berg, Paul Saikko, and Matti Järvisalo. SAT 2017.
Preprints and manuscripts
- New Width Parameters for Independent Set: One-sided-mim-width and Neighbor-depth. with Benjamin Bergougnoux and Igor Razgon. 2023.
- Computing Tree Decompositions with Small Independence Number. with Clément Dallard, Fedor V. Fomin, Petr A. Golovach, and Martin Milanič. 2022.
- Listing Small Minimal Separators of a Graph. 2020.
- Tight Bounds for Potential Maximal Cliques Parameterized by Vertex Cover. 2020.
Talks
- Shortest Cycles With Monotone Submodular Costs. (slides) at SODA 2023.
- An Improved Parameterized Algorithm for Treewidth.
- Princeton Discrete Mathematics Seminar (slides)
- Jagiellonian University TCS seminar (slides, video)
- Helsinki CS Theory Seminar (slides)
- UCSB CS Theory Colloquium (slides)
- Graph Decompositions: Small Width, Big Challenges (slides)
- Computing Tree Decompositions with Small Independence Number.
- Dagstuhl Seminar: Vertex Partitioning in Graphs: From Structure to Algorithms (slides)
- GROW 2022 (slides)
- Fixed-Parameter Tractability of Maximum Colored Path and Beyond.
- Grid Induced Minor Theorem for Graphs of Small Degree. (slides) at CSGT 2022.
- Fast FPT 2-Approximation Algorithms for Width Parameters. (slides) at PAAW 2022.
- Fast FPT-Approximation of Branchwidth.
- STOC 2022 (slides, video, poster)
- APGA 2022 (slides)
- Workshop on Parametrized complexity and discrete optimization at Hausdorff Research Institute for Mathematics, 12/2021, (slides, video)
- IBS Virtual Discrete Math Colloquium, 11/2021, (slides)
- A Single-Exponential Time 2-Approximation Algorithm for Treewidth.
- FOCS 2021, (slides, video)
- seminar of AlGCo, 1/2022, (slides)
- Frontiers of Parameterized Complexity, 5/2021, (slides, video)
- 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.
- 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
- Model Counting Competition, in 2021 first place on tracks 1, 2, and 4, in 2022 first place on track 2 and second place on track 1.
- 2nd place in PACE 2020, exact treedepth track.
- 2nd place in PACE 2017, exact minimum fill-in track.
Reviewing
- Conferences: ICALP 2023, STOC 2023, LATIN 2022, ESA 2022, MFCS 2022, WG 2022, SWAT 2022, ICALP 2022, STOC 2022, AAAI 2022, SAT 2021, ICALP 2021, AAAI 2021, MFCS 2020, SAT 2020
- Journals: SIAM Journal on Computing, Journal of Combinatorial Theory Series B, SIAM Journal on Discrete Mathematics, Discrete Applied Mathematics, 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.
Updated on 6 March 2023