Institute of Mathematics

Objectives:

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:  

Chatterjee Prerona Folwarczný Lukáš Gavinsky Dmytro

Khaniki Erfan Pudlák Pavel Talebanfard Navid

 Participating institutions:

Faculty of Mathematics and Physics, Charles University (Coordinator)
Institute of Mathematics, Czech Academy of Sciences

    Mapa   |  Autor   |  Webmaster