**Chair for**** Algorithm Engineering**

Hasso Plattner Institute

Office: K-2.06

Tel.:

E-Mail: Kirill.Simonov(at)hpi.de

Links: Homepage, Publications

# Research Interests

My main focus lies in extending the parameterized complexity paradigm to new domains, especially to non-discrete problems such as clustering. I enjoy coupling combinatorial tools with randomized/approximate/algebraic techniques. My main topics include:

- Parameterized algorithms
- Approximation algorithms
- Graph theory
- Learning theory

## Publications

2024 [ nach oben ]

- "Horev, Yinon"; "Shay, Shiraz"; "Cohen, Sarel"; "Friedrich, Tobias"; "Issac, Davis"; "Kamma, Lior"; "Niklanovits, Aikaterini"; "Simonov, Kirill"
**A Contraction Tree SAT Encoding for Computing Twin-Width**2024 - Fomin, Fedor V.; Golovach, Petr A.; Sagunov, Danil; Simonov, Kirill
**Tree Containment Above Minimum Degree is FPT**Symposium on Discrete Algorithms (SODA) 2024: 366–376

2023 [ nach oben ]

- Blažej, Václav; Ganian, Robert; Knop, Dušan; Pokorný, Jan; Schierreich, Šimon; Simonov, Kirill
**The Parameterized Complexity of Network Microaggregation**Conference on Artificial Intelligence (AAAI) 2023: 6262–6270 - Brand, Cornelius; Ganian, Robert; Simonov, Kirill
**A Parameterized Theory of PAC Learning**Conference on Artificial Intelligence (AAAI) 2023: 6834–6841 - Jansen, Bart M. P.; Khazaliya, Liana; Kindermann, Philipp; Liotta, Giuseppe; Montecchiani, Fabrizio; Simonov, Kirill
**Upward and Orthogonal Planarity are W[1]-Hard Parameterized by Treewidth**Graph Drawing (GD) 2023: 203–217 - Fomin, Fedor; Golovach, Petr; Sagunov, Danil; Simonov, Kirill
**Approximating Long Cycle Above Dirac’s Guarantee**International Colloquium on Automata, Languages and Programming (ICALP) 2023: 60:1–60:18 - Ganian, Robert; Khazaliya, Liana; Simonov, Kirill
**Consistency Checking Problems: A Gateway to Parameterized Sample Complexity**International Symposium on Parameterized and Exact Computation (IPEC) 2023: 18:1–18:17 - Khazaliya, Liana; Kindermann, Philipp; Liotta, Giuseppe; Montecchiani, Fabrizio; Simonov, Kirill
**The st-Planar Edge Completion Problem Is Fixed-Parameter Tractable**International Symposium Algorithms and Computation (ISAAC) 2023: 46:1–46:13 - Fomin, Fedor V.; Golovach, Petr A.; Korhonen, Tuukka; Simonov, Kirill; Stamoulis Giannοs
**Fixed-Parameter Tractability of Maximum Colored Path and Beyond**Symposium on Discrete Algorithms (SODA) 2023 - Bandyapadhyay, Sayan; Fomin, Fedor V.; Inamdar, Tanmay; Panolan, Fahad; Simonov, Kirill
**Socially Fair Matching: Exact and Approximation Algorithms**Workshop on Algorithms and Data Structures (WADS) 2023: 79–92 - Bandyapadhyay, Sayan; Fomin, Fedor V.; Inamdar, Tanmay; Simonov, Kirill
**Proportionally Fair Matching with Multiple Groups**Workshop on Graph-Theoretic Concepts in Computer Science (WG) 2023: 1–15 - Fomin, Fedor; Golovach, Petr; Sagunov, Danil; Simonov, Kirill
**Turán’s Theorem Through Algorithmic Lens**Workshop on Graph-Theoretic Concepts in Computer Science (WG) 2023: 348–362

2022 [ nach oben ]

- Bandyapadhyay, Sayan; Fomin, Fedor V.; Golovach, Petr A.; Lochet, William; Purohit, Nidhi; Simonov, Kirill
**How to Find a Good Explanation for Clustering?**Conference on Artificial Intelligence (AAAI) 2022: 3904–3912 - Fomin, Fedor V.; Golovach, Petr A.; Sagunov, Danil; Simonov, Kirill
**Algorithmic Extensions of Dirac’s Theorem**Symposium on Discrete Algorithms (SODA) 2022: 406–416