Circuit Complexity and Self-Reducibility
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 13 (SGA02010GA-ST)
Main participants
—
Contest type
VS - Public tender
Contract ID
P202-10-0854
Alternative language
Project name in Czech
Obvodová složitost a samo-převeditelnost
Annotation in Czech
Tento projekt navrhuje studovat dvě úzce související oblasti výpočetní složitosti: obvody omezené hloubky a samo-převeditelnost funkcí. V oblasti obvodů omezené hloubky se chceme soustředit na studium tříd funkcí počitatelných obvody malé polynomiální velikosti, na vztah mezi hloubkou obvodu a jeho velikostí a na ekvivalenci obvodových tříd. V oblasti samo-převeditelnosti se zaměříme na studium samo-převeditelnosti problémů na menší instance a na tzv. kompresi instancí. Hlavním cílem projektu je přinéstdalší porozumění tříd funkcí počitatelných obvody omezené hloubky a jejich vztahu k větším výpočetním třídám.
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
IN - Informatics
CEP - secondary branch
—
CEP - another secondary branch
—
OECD FORD - equivalent branches <br>(according to the <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">converter</a>)
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Completed project evaluation
Provider evaluation
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Project results evaluation
The main results of the project are in the area of computational complexity. The project output includes papers in top journals and leading conferences (such as STOC). The overall quality of the results is impressive (for example, a 30-year old open problem in the area of on-line labeling algorithms has been solved). Financial resources have been used efficiently.
Solution timeline
Realization period - beginning
Jan 1, 2010
Realization period - end
Dec 31, 2012
Project status
U - Finished project
Latest support payment
Apr 1, 2012
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
CEP13-GA0-GA-U/02:3
Data delivery date
May 17, 2016
Finance
Total approved costs
926 thou. CZK
Public financial support
926 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK