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
Workshops
- EPAC Workshop: Algorithms and Complexity, 28-31 May 2023, Špindlerův Mlýn, Czech Republic
- Workshop: Complexity Theory with a Human Face, 3rd Edition, 27 June - 1 July, 2022, Prague and Špindlerův Mlýn, Czech Republic
- Workshop: Complexity Theory with a Human Face, 2nd Edition, 17-20 October 2021, Špindlerův Mlýn, Czech Republic
- Workshop: Complexity Theory with a Human Face, 1-4 September 2020 Tábor, Czech Republic
 |
This project is funded by the Grant Agency of the Czech Republic under the grant agreement no. 19-27871X. |