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 :
Main investigator:
Koucký Michal
IM team members:
|
Folwarczný Lukáš Gavinsky Dmitry Khaniki Erfan |
Pudlák Pavel Talebanfard Navid |
Participating institutions:
Faculty of Mathematics and Physics, Charles University (Coordinator)
Institute of Mathematics, Czech Academy of Sciences
