Enumerace v informatice a optimalizaci

Poskytovatel

Grantová agentura České republiky

Program

Standardní projekty

Veřejná soutěž

Standardní projekty 17 (SGA0201300005)

Hlavní účastníci

Univerzita Karlova / Matematicko-fyzikální fakulta

Druh soutěže

VS - Veřejná soutěž

Číslo smlouvy

13-21988S

Název projektu anglicky

Enumeration in informatics and optimization

Anotace anglicky

The aim of this project is to make substantial advances in Theoretical Computer Science and Optimization by using recently developed enumerative methods. The project has three parts. First, we want to contribute to theory of computational intractability by studying complexity lower bounds. We want to relate additive determinantal complexity, where exponential lower bound (co-authored by me) was established recently in terms of Arf-invariant formula and proof of Norine' s conjecture for the Ising partition function, to determinantal complexity. Secondly, we want to advance understanding complexity of graph isomorphism by studying the conjecture that non-isomorphic chordal graphs are detected by the partition function of the Potts model in variable magnetic field; this function is equivalent to a decorated Tutte polynomial, and isomorphism problem of general graphs is equivalent to isomorphism problem for chordal graphs. Finally, we want to deepen connections between Computing and Physics. Specifically we study classic and quantum Ising problem computation.

Kategorie VaV

ZV - Základní výzkum

CEP - hlavní obor

IN - Informatika

CEP - vedlejší obor

—

CEP - další vedlejší obor

—

OECD FORD - odpovídající obory <br>(dle <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">převodníku</a>)

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Hodnocení poskytovatelem

U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)

Zhodnocení výsledků projektu

Projekt přinesl nové výsledky v některých oblastech návrhu. Řešitel předložil přínos publikovaných výsledků, výsledky byly zveřejněné ve třech hlavních publikacích. Řešitel se nevěnoval plnění všech původně navržených cílů projektu (např. kvantové počítání), aniž by vysvětlil důvod, kvalita publikací je spíše průměrná.

Zahájení řešení

1. 2. 2013

Ukončení řešení

25. 4. 2019

Poslední stav řešení

U - Ukončený projekt

Poslední uvolnění podpory

11. 4. 2017

Důvěrnost údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Systémové označení dodávky dat

CEP20-GA0-GA-U/01:1

Datum dodání záznamu

2. 7. 2020

Celkové uznané náklady

2 577 tis. Kč

Výše podpory ze státního rozpočtu

2 577 tis. Kč

Ostatní veřejné zdroje financování

0 tis. Kč

Neveřejné tuz. a zahr. zdroje finan.

0 tis. Kč