About: Circuit Complexity and Self-Reducibility

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

About: Circuit Complexity and Self-Reducibility 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=GAP202/10/0854
Description	The project proposes to study two areas of computational complexity: circuits of bounded depth and self-reducibility of functions. In the area of circuits of bounded depth we aim to study the class of functions computed by small-polynomial size circuits, the relationship between depth and size of circuits, and equivalence of circuit classes. In the area of self-reducibility we intend to study downward self-reducibility and instance compression. The main goal of the project is to bring further understanding of classes of functions computed by small depth circuits and their relationship to larger complexity classes. (en) Tento projekt navrhuje studovat dvě úzce související oblasti výpočetní složitosti: obvody omezené hloubky a samo-převeditelnost funkcí. V oblasti obvodů omezené hloubky se chceme soustředit na studium tříd funkcí počitatelných obvody malé polynomiální velikosti, na vztah mezi hloubkou obvodu a jeho velikostí a na ekvivalenci obvodových tříd. V oblasti samo-převeditelnosti se zaměříme na studium samo-převeditelnosti problémů na menší instance a na tzv. kompresi instancí. Hlavním cílem projektu je přinést další porozumění tříd funkcí počitatelných obvody omezené hloubky a jejich vztahu k větším výpočetním třídám.
Title	Circuit Complexity and Self-Reducibility (en) Obvodová složitost a samo-převeditelnost
skos:notation	GAP202/10/0854
http://linked.open...avai/cep/aktivita	Standard projects
http://linked.open...kovaStatniPodpora	http://linked.opendata.cz/resource/domain/vavai/projekt/GAP202%2F10%2F0854/celkovaStatniPodpora
http://linked.open...ep/celkoveNaklady	http://linked.opendata.cz/resource/domain/vavai/projekt/GAP202%2F10%2F0854/celkoveNaklady
http://linked.open...datumDodatniDoRIV	2014-01-30 (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	92536441
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	circuit; complexity; bounded-depth; circuits; self-reducibility; instance; compression (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	10 (xsd:int)
http://linked.open...enychVysledkuVRIV	10 (xsd:int)
http://linked.open...lneniVMinulemRoce	2012-03-30 (xsd:date)
http://linked.open.../prideleniPodpory	http://linked.opendata.cz/resource/domain/vavai/cep/prideleniPodpory/P202%2F10%2F0854
http://linked.open...iciPoslednihoRoku	2012
http://linked.open...atUdajeProjZameru	2013
http://linked.open.../vavai/cep/soutez	SGA02010GA-ST
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	2012-12-31 (xsd:date)
http://linked.open...ep/zahajeniReseni	2010-01-01 (xsd:date)
http://linked.open...jektu+dodavatelem	Hlavní výsledky projektu spadají do oblasti výpočetní složitosti a jsou adekvátně popsány v závěrečné kartě. Přes nízký rozpočet projektu se do jeho řešení zapojil i jeden doktorand. Výsledky projektu jsou po stránce kvality impresivní, byl mimo jiné vyřešen dlouho otevřený problém týkající se algoritmů pro tzv. %22on-line labeling%22. Finanční prostředky byly vynaloženy účelně. (cs) The main results of the project are in the area of computational complexity. The project output includes papers in top journals and leading conferences (such as STOC). The overall quality of the results is impressive (for example, a 30-year old open problem in the area of on-line labeling algorithms has been solved). Financial resources have been used efficiently. (en)
http://linked.open...tniCyklusProjektu	ZBKU
http://linked.open.../cep/klicoveSlovo	circuit bounded-depth circuits complexity instance self-reducibility
is http://linked.open...vavai/riv/projekt of	The hardness of being private Tight lower bounds for the online labeling problem Exact algorithms for solving stochastic games The hardness of being private The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory Pseudorandom generators for group products On online labeling with polynomially many labels Derandomizing from random strings A New Characterization of ACC(0) and Probabilistic CC0 Amplifying lower bounds by means of self-reducibility
is http://linked.open...vavai/cep/projekt of	http://linked.opendata.cz/resource/domain/vavai/cep/ucast/GAP202%2F10%2F0854/2010/ico%3A67985840 http://linked.opendata.cz/resource/domain/vavai/cep/ucast/GAP202%2F10%2F0854/2011/ico%3A67985840 http://linked.opendata.cz/resource/domain/vavai/cep/ucast/GAP202%2F10%2F0854/2012/ico%3A67985840 http://linked.opendata.cz/resource/domain/vavai/cep/ucast/GAP202%2F10%2F0854/2013/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, 112 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software