Research

We are interested in the design, theoretical analysis, and experimental evaluation of algorithms for a broad range of computational problems. Our main focus lies on NP-hard problems. In general, these problems have no efficient algorithms but many real-world instances can be usually solved quite efficiently. Typical problems considered in our research arise in different areas of data science such as

• Network analysis - graph clustering, community detection,
• Machine learning - decision trees, Bayesian networks,
• Computational biology - string algorithms, phylogenetics.

From the methodological side, we are interested in 

• Fine-Grained Running Time Lower Bounds - determining precisely how fast certain problems can be solved, 
• Parameterized Algorithmics - analyzing the influence of parameters that describe structural properties of the input on the difficulty to solve the problem,
• Kernelization and Data Reduction - developing efficient preprocessing rules that shrink or simplify the instances,
• Algorithm Engineering - analyzing and improving the practical performance of algorithms by identifying heuristic speed-ups, using efficient data structures, and recognizing current bottlenecks for better perfomance.