Výpočetní a komunikační složitost Booleovských funkcí a derandomizace

Název projektu anglicky
Computational and communication complexity of Boolean functions, and derandomization
Anotace anglicky
The project proposes to study three related areas of computational complexity: circuit and branching program lower bounds, multi-party communication complexity and derandomization. In the first area we propose to study the size of bounded-depth countingcircuits and the depth of Boolean circuits needed to compute explicit functions. Furthermore, we propose to study the recently introduced variants of branching programs---incremental and tight branching programs. In the area of multiparty communication complexity we want to focus on the relationship among deterministic, nondeterministic and randomized protocols. In the area of derandomization we want to consider several key problems related to derandomization of space-bounded computation.

Kategorie VaV
ZV - Základní výzkum
CEP - hlavní obor
IN - Informatika
CEP - vedlejší obor
BD - Teorie informace
CEP - další vedlejší obor
BA - Obecná matematika
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>)
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)

Hodnocení poskytovatelem
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Zhodnocení výsledků projektu
Řešitel se výzkumných úkolů zhostil vynikajícím způsobem a dosažené výsledky mají světovou úroveň. Tomuto hodnocení odpovídají i publikační výstupy. Úctyhodná je nejen jejich kvantita, ale především kvalita. Konference typu CCC nebo LICS se zcela jistě ?

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
CEP10-GA0-GP-U/03:3
Datum dodání záznamu
1. 3. 2016

Podobné projekty(10)