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

Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture
Original language description
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.
Czech name
—
Czech description
—

Project
<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

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

Article name in the collection
Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014)
ISBN
978-1-4503-2710-7
ISSN
—
e-ISSN
—
Number of pages
10
Pages from-to
213-222
Publisher name
ACM
Place of publication
New York
Event location
New York
Event date
May 31, 2014
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)