Kirill Simonov
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
2025
Niklanovits, Aikaterini; Simonov, Kirill; Verma, Shaily; Zeif, ZienaConnected Partitions via Connected Dominating SetsEuropean Symposium on Algorithms (ESA) 2025
[ ][ ][ Download ]
2024
Horev, Yinon; Shay, Shiraz; Cohen, Sarel; Friedrich, Tobias; Issac, Davis; Kamma, Lior; Niklanovits, Aikaterini; Simonov, KirillA Contraction Tree SAT Encoding for Computing Twin-WidthAdvances in Knowledge Discovery and Data Mining 2024
Casel, Katrin; Friedrich, Tobias; Niklanovits, Aikaterini; Simonov, Kirill; Zeif, ZienaCombining Crown Structures for Vulnerability MeasuresInternational Symposium on Parameterized and Exact Computation (IPEC) 2024: 1:1–1:15
Best Paper Award
Fomin, Fedor V.; Golovach, Petr A.; Sagunov, Danil; Simonov, KirillTree Containment Above Minimum Degree is FPTSymposium on Discrete Algorithms (SODA) 2024: 366–376
2023
Blažej, Václav; Ganian, Robert; Knop, Dušan; Pokorný, Jan; Schierreich, Šimon; Simonov, KirillThe Parameterized Complexity of Network MicroaggregationConference on Artificial Intelligence (AAAI) 2023: 6262–6270
Brand, Cornelius; Ganian, Robert; Simonov, KirillA Parameterized Theory of PAC LearningConference on Artificial Intelligence (AAAI) 2023: 6834–6841
Jansen, Bart M. P.; Khazaliya, Liana; Kindermann, Philipp; Liotta, Giuseppe; Montecchiani, Fabrizio; Simonov, KirillUpward and Orthogonal Planarity are W[1]-Hard Parameterized by TreewidthGraph Drawing (GD) 2023: 203–217
Fomin, Fedor; Golovach, Petr; Sagunov, Danil; Simonov, KirillApproximating Long Cycle Above Dirac’s GuaranteeInternational Colloquium on Automata, Languages and Programming (ICALP) 2023: 60:1–60:18
Ganian, Robert; Khazaliya, Liana; Simonov, KirillConsistency Checking Problems: A Gateway to Parameterized Sample ComplexityInternational Symposium on Parameterized and Exact Computation (IPEC) 2023: 18:1–18:17
Khazaliya, Liana; Kindermann, Philipp; Liotta, Giuseppe; Montecchiani, Fabrizio; Simonov, KirillThe st-Planar Edge Completion Problem Is Fixed-Parameter TractableInternational Symposium Algorithms and Computation (ISAAC) 2023: 46:1–46:13
Fomin, Fedor V.; Golovach, Petr A.; Korhonen, Tuukka; Simonov, Kirill; Stamoulis GiannοsFixed-Parameter Tractability of Maximum Colored Path and BeyondSymposium on Discrete Algorithms (SODA) 2023
Bandyapadhyay, Sayan; Fomin, Fedor V.; Inamdar, Tanmay; Panolan, Fahad; Simonov, KirillSocially Fair Matching: Exact and Approximation AlgorithmsWorkshop on Algorithms and Data Structures (WADS) 2023: 79–92
Bandyapadhyay, Sayan; Fomin, Fedor V.; Inamdar, Tanmay; Simonov, KirillProportionally Fair Matching with Multiple GroupsWorkshop on Graph-Theoretic Concepts in Computer Science (WG) 2023: 1–15
Fomin, Fedor; Golovach, Petr; Sagunov, Danil; Simonov, KirillTurán’s Theorem Through Algorithmic LensWorkshop on Graph-Theoretic Concepts in Computer Science (WG) 2023: 348–362
2022
Bandyapadhyay, Sayan; Fomin, Fedor V.; Golovach, Petr A.; Lochet, William; Purohit, Nidhi; Simonov, KirillHow to Find a Good Explanation for Clustering?Conference on Artificial Intelligence (AAAI) 2022: 3904–3912
Fomin, Fedor V.; Golovach, Petr A.; Sagunov, Danil; Simonov, KirillAlgorithmic Extensions of Dirac’s TheoremSymposium on Discrete Algorithms (SODA) 2022: 406–416