Efficient approximation algorithms and circuit complexity
Project goals
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.
Keywords
approximation algorithmsfine-grained complexityparameterized complexityEdit distanceInteger ProgrammingSATcircuitslower bounds
Public support
Provider
Czech Science Foundation
Programme
Grant projects of excellence in basic research EXPRO
Call for proposals
Grantové projekty excelence v základním výzkumu EXPRO (SGA0201900004)
Main participants
Univerzita Karlova / Matematicko-fyzikální fakulta
Contest type
VS - Public tender
Contract ID
19-27871X
Alternative language
Project name in Czech
Efektivní aproximační algoritmy a obvodová složitost
Annotation in Czech
Tento projekt bude studovat roli aproximace v oblasti jemné složitosti a parametrizované složitosti a zároveň vytvoří důkladné základy těchto oblastí nalezením důkazových technik schopných dokázat pravdivost klíčových předpokladů používaných v těchto oblastech. Studium se soustředí na několik klíčových problémů: editační vzdálenost, celočíselné programování, splnitelnost a jejich aproximační a parametrizované algoritmy. Cílem je nalezení nejlepších možných algoritmů pro tyto a další problémy. Též se zaměříme na několik důkazových metod pro dolní odhady.
Scientific branches
R&D category
ZV - Basic research
OECD FORD - main branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
OECD FORD - secondary branch
—
OECD FORD - another secondary branch
—
AF - Documentation, librarianship, work with information
BC - Theory and management systems
BD - Information theory
IN - Informatics
Solution timeline
Realization period - beginning
Jan 1, 2019
Realization period - end
Jun 30, 2024
Project status
—
Latest support payment
Apr 1, 2024
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP25-GA0-GX-R
Data delivery date
Mar 12, 2025
Finance
Total approved costs
49,235 thou. CZK
Public financial support
49,235 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
49 235 CZK thou.
Public support
49 235 CZK thou.
100%
Provider
Czech Science Foundation
OECD FORD
Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Solution period
01. 01. 2019 - 30. 06. 2024