About Me
I am a Project Assistant Professor (特任助教) at the University of Tokyo. My research is in theoretical computer science, especially the design and analysis of algorithms for NP-hard problems. I am currently interested in algebraic methods for faster exponential-time algorithms, parameterized and exact algorithms, graph and matroid algorithms, counting problems, derandomization, and time-space tradeoffs.
Education
Technische Universität Berlin
PhD in Computer Science
February 2020 - January 2024
Thesis: New Parameterized Algorithms for Matching and Packing Problems.
Advisor: Prof. Rolf Niedermeier.
Technische Universität Berlin
MSc in Computer Science
October 2017 - December 2019
Thesis: Algorithmic and Structural Aspects of Matrix Completion Problems.
Advisor: Prof. Rolf Niedermeier.
The University of Tokyo
BEng in Information and Communication Engineering
April 2013 - March 2017
Thesis: An analytic approach for statistical properties of stochastic oscillators and its application.
Advisor: Prof. Yoshihiko Hasegawa.
Selected Publications
See DBLP or Google Scholar for complete publication lists.
Determinantal Sieving
Eduard Eiben, Tomohiro Koana, Magnus Wahlström.
TheoretiCS 2025 |
SODA 2024
Introduces determinantal sieving, an algebraic framework for parameterized algorithms over linear matroids. The method extends multilinear detection to matroidal constraints and gives cleaner or faster algorithms for a range of problems.
Faster Edge Coloring by Partition Sieving
Shyan Akmal, Tomohiro Koana.
STACS 2025
Gives an exact algorithm for Edge Coloring that improves over the standard 2^m-time baseline while using only polynomial space. The result is a step toward faster exact algorithms for one of the classical NP-hard coloring problems.
Induced Matching Below Guarantees: Average Paves the Way for Fixed-Parameter Tractability
Tomohiro Koana.
STACS 2023
Studies below-guarantee parameterizations of Induced Matching. The paper shows that two natural smaller guarantees are unlikely to yield fixed-parameter tractability on their own, but that their average does lead to an FPT branching algorithm using Gallai-Edmonds decomposition.
The Complexity of Finding Fair Many-To-One Matchings
Niclas Boehmer, Tomohiro Koana.
ACM Transactions on Algorithms 2024 |
ICALP 2022
Analyzes fair variants of bipartite many-to-one matching where colors model attributes. The paper proves hardness even under strong restrictions, gives FPT algorithms for structural parameters, and uses integer programs based on Hall-type conditions and a separation theorem inspired by Frank’s work.
Exploiting c-Closure in Kernelization Algorithms for Graph Problems
Tomohiro Koana, Christian Komusiewicz, Frank Sommer.
SIAM Journal on Discrete Mathematics 2022 |
ESA 2020
Applies the c-closed graph model to kernelization for classic graph problems. The key ingredient is a polynomial Ramsey-type bound for c-closed graphs, which yields fixed-parameter algorithms and polynomial kernels for problems such as Dominating Set and Induced Matching.