All
All

What are you looking for?

All
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

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