It is necessary to activate JavaScript to navigate this site.

Grant 19-27871X     1.1.2019 - 31.12.2023
Grantor: Czech Science Foundation

Efficient approximation algorithms and circuit complexity


The goal of this project is to understand the role of approximation in fine-grained and parameterized complexity and create solid foundations for these areas by developing lower bound techniques capable of addressing the key unproven assumptions under-pinning these areas. We will focus on several central problems: Edit Distance, Integer Programming, Satisfiability and study their approximation and parameterized algorithms with the aim of
designing the best possible algorithms. Additionally we will focus on several methods of proving complexity lower bounds.

  IM leader :

Hrubeš Pavel

  Main investigator:

Koucký  Michal

 IM team members:  
Gavinsky Dmitry
Pudlák Pavel