EPAC: Efficient approximation algorithms and circuit complexity

GA CR EXPRO project

"Efficient approximation algorithms and circuit complexity" is a five year project funded by the Grant Agency of the Czech Republic as an EXPRO grant. Its principal investigators are Michal Koucký and Pavel Hrubeš. The project is co-hosted by the Computer Science Institute of Charles University and the Institute of Mathematics of the Academy of Sciences of the Czech Republic. The project started in January 2019.

Scientific goals of the project

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. The project focuses 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 the project also focuses on several methods of proving complexity lower bounds.

List of outcomes


This project is funded by the Grant Agency of the Czech Republic under the grant agreement no. 19-27871X.