Computational and communication complexity of Boolean functions, and derandomization
Public support
Provider
Czech Science Foundation
Programme
Post-graduate (doctorate) grants
Call for proposals
Postdoktorandské granty 7 (SGA02007GA1PD)
Main participants
—
Contest type
VS - Public tender
Contract ID
201/07/P276
Alternative language
Project name in Czech
Výpočetní a komunikační složitost Booleovských funkcí a derandomizace
Annotation in Czech
Tento projekt navrhuje studovat tři úzce související oblasti výpočetní složitosti: dolní odhady pro obvody a rozhodovací diagramy, komunikační složitost více hráčů a derandomizaci. V první oblasti navrhujeme studium velikosti početních obvodů omezené hloubky a hloubky Booleovských obvodů potřebných pro vyhodnocování explicitních funkcí. Dále pak navrhujeme studium nedávno zavedených druhů rozhodovacích diagramů, inkrementálních a těsných rozhodovacích diagramů. V oblasti komunikační složitosti více hráčů navrhujeme analyzovat vztah mezi deterministickými, nedeterministickými a pravděpodobnostními protokoly. V oblasti derandomizace se chceme soustředit na studium několika klíčových problémů derandomizace výpočtů běžících v omezeném prostoru.
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
IN - Informatics
CEP - secondary branch
BD - Information theory
CEP - another secondary branch
BA - General mathematics
OECD FORD - equivalent branches <br>(according to the <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">converter</a>)
10101 - Pure mathematics<br>10102 - Applied mathematics<br>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
.
Solution timeline
Realization period - beginning
Jan 1, 2007
Realization period - end
Dec 31, 2009
Project status
U - Finished project
Latest support payment
Apr 22, 2009
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
CEP10-GA0-GP-U/03:3
Data delivery date
Mar 1, 2016
Finance
Total approved costs
606 thou. CZK
Public financial support
606 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK