About: Computational and communication complexity of Boolean functions, and derandomization

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Computational and communication complexity of Boolean functions, and derandomization Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Projekt, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	http://linked.opendata.cz/ontology/domain/vavai/Projekt
rdfs:seeAlso	http://www.isvav.cz/projectDetail.do?rowId=GP201/07/P276
Description	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 counting circuits 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. (en) 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.
Title	Computational and communication complexity of Boolean functions, and derandomization (en) Výpočetní a komunikační složitost Booleovských funkcí a derandomizace
skos:notation	GP201/07/P276
http://linked.open...avai/cep/aktivita	Post-graduate (doctorate) grants
http://linked.open...kovaStatniPodpora	http://linked.opendata.cz/resource/domain/vavai/projekt/GP201%2F07%2FP276/celkovaStatniPodpora
http://linked.open...ep/celkoveNaklady	http://linked.opendata.cz/resource/domain/vavai/projekt/GP201%2F07%2FP276/celkoveNaklady
http://linked.open...datumDodatniDoRIV	2015-01-22 (xsd:date)
http://linked.open...i/cep/druhSouteze	VS - Veřejná soutěž ve výzkumu a vývoji
http://linked.open...ep/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open.../cep/fazeProjektu	65824822
http://linked.open...ai/cep/hlavniObor	IN - Informatika
http://linked.open...hodnoceniProjektu	V - Vynikající výsledky (s mezinárodním významem apod.). Zároveň byly splněny cíle a předpokládané výsledky uvedené ve smlouvě / rozhodnutí o poskytnutí podpory.
http://linked.open...vai/cep/kategorie	ZV - Základní výzkum
http://linked.open.../cep/klicovaSlova	branching programs; Boolean circuits; communication complexity; derandomization (en)
http://linked.open...ep/partnetrHlavni	Matematický ústav AV ČR, v. v. i.
http://linked.open...inujicichPrijemcu	0 (xsd:int)
http://linked.open...cep/pocetPrijemcu	1 (xsd:int)
http://linked.open...ocetSpoluPrijemcu	0 (xsd:int)
http://linked.open.../pocetVysledkuRIV	13 (xsd:int)
http://linked.open...enychVysledkuVRIV	13 (xsd:int)
http://linked.open...lneniVMinulemRoce	2009-04-22 (xsd:date)
http://linked.open.../prideleniPodpory	http://linked.opendata.cz/resource/domain/vavai/cep/prideleniPodpory/201%2F07%2FP276
http://linked.open...iciPoslednihoRoku	2009
http://linked.open...atUdajeProjZameru	2010
http://linked.open.../vavai/cep/soutez	SGA02007GA1PD
http://linked.open...usZobrazovaneFaze	DUU
http://linked.open...ai/cep/typPojektu	P - Projekt výzkumu a vývoje financovaný ze státního rozpočtu
http://linked.open...ep/ukonceniReseni	2009-12-31 (xsd:date)
http://linked.open.../cep/vedlejsiObor	BD - Teorie informace BA - Obecná matematika
http://linked.open...ep/zahajeniReseni	2007-01-01 (xsd:date)
http://linked.open...jektu+dodavatelem	. (en) Ř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ě ve (cs)
http://linked.open...tniCyklusProjektu	ZBKU
http://linked.open.../cep/klicoveSlovo	branching programs Boolean circuits communication complexity
is http://linked.open...vavai/cep/projekt of	http://linked.opendata.cz/resource/domain/vavai/cep/ucast/GP201%2F07%2FP276/2007/ico%3A67985840 http://linked.opendata.cz/resource/domain/vavai/cep/ucast/GP201%2F07%2FP276/2008/ico%3A67985840 http://linked.opendata.cz/resource/domain/vavai/cep/ucast/GP201%2F07%2FP276/2009/ico%3A67985840 http://linked.opendata.cz/resource/domain/vavai/cep/ucast/GP201%2F07%2FP276/2010/ico%3A67985840

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 47 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software