Computational and communication complexity of Boolean functions, and derandomization
Project goals
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.
Keywords
branching programsBoolean circuitscommunication complexityderandomization
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
10101 - Pure mathematics
10102 - Applied mathematics
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
Basic information
Recognised costs
606 CZK thou.
Public support
606 CZK thou.
100%
Provider
Czech Science Foundation
CEP
IN - Informatics
Solution period
01. 01. 2007 - 31. 12. 2009