Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F14%3A00434460" target="_blank" >RIV/67985840:_____/14:00434460 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture

Popis výsledku v původním jazyce

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., ...). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, it is one of the first milestones toward proving super-polynomial circuit lower bounds. In this work, we make a natural step in this direction, which lies between what is known and the original conjecture: we show that an analogue of the KRW Composition Conjecture holds for the composition of a function with a universal relation.

Název v anglickém jazyce

Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture

Popis výsledku anglicky

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., ...). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, it is one of the first milestones toward proving super-polynomial circuit lower bounds. In this work, we make a natural step in this direction, which lies between what is known and the original conjecture: we show that an analogue of the KRW Composition Conjecture holds for the composition of a function with a universal relation.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2014

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014)

ISBN

978-1-4503-2710-7

ISSN

—

e-ISSN

—

Počet stran výsledku

10

Strana od-do

213-222

Název nakladatele

ACM

Místo vydání

New York

Místo konání akce

New York

Datum konání akce

31. 5. 2014

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—