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)

AttributesValues
rdf:type
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. (cs)
Title
  • Výpočetní a komunikační složitost Booleovských funkcí a derandomizace (cs)
  • Computational and communication complexity of Boolean functions, and derandomization (en)
http://linked.open...vai/cislo-smlouvy
http://linked.open...lsi-vedlejsi-obor
http://linked.open...avai/druh-souteze
http://linked.open...domain/vavai/faze
http://linked.open...vavai/hlavni-obor
http://linked.open...vai/vedlejsi-obor
http://linked.open...vavai/id-aktivity
http://linked.open.../vavai/id-souteze
http://linked.open...n/vavai/kategorie
http://linked.open...vai/klicova-slova
  • branching programs; Boolean circuits; communication complexity; derandomization (en)
http://linked.open...avai/konec-reseni
http://linked.open...nujicich-prijemcu
http://linked.open...avai/poskytovatel
http://linked.open...avai/start-reseni
http://linked.open...ai/statni-podpora
http://linked.open...vavai/typProjektu
http://linked.open...ai/uznane-naklady
http://linked.open...ai/pocet-prijemcu
http://linked.open...cet-spoluprijemcu
http://linked.open...ai/pocet-vysledku
http://linked.open...ku-zverejnovanych
is http://linked.open...ain/vavai/projekt of
Faceted Search & Find service v1.16.118 as of Jun 21 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
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, 39 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software