Počet záznamů: 1
Toward better formula lower bounds: The composition of a function and a universal relation
- 1.
SYSNO ASEP 0473043 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název Toward better formula lower bounds: The composition of a function and a universal relation Tvůrce(i) Gavinsky, Dmitry (MU-W) RID, SAI, ORCID
Meir, O. (IL)
Weinstein, O. (US)
Wigderson, A. (US)Zdroj.dok. Siam Journal on Computing - ISSN 0097-5397
Roč. 46, č. 1 (2017), s. 114-131Poč.str. 18 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova formula ; Karchmer-Wigderson relations ; lower bounds Vědní obor RIV BA - Obecná matematika Obor OECD Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8) CEP GBP202/12/G061 GA ČR - Grantová agentura ČR Institucionální podpora MU-W - RVO:67985840 UT WOS 000396677400006 EID SCOPUS 85014494342 DOI https://doi.org/10.1137/15M1018319 Anotace One of the major open problems in complexity theory is proving superlogarithmic lower bounds on the depth of circuits (i.e., P ... NC1). 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 superpolynomial circuit lower bounds. Karchmer, Raz, and Wigderson [Comput. Complexity, 5 (1995), pp. 191-204] suggested approaching this problem by proving the following conjecture: given two Boolean functions f and g, the depth complexity of the composed function g ... f is roughly the sum of the depth complexities of f and g. They showed that the validity of this conjecture would imply that P ... NC1. As a starting point for studying the composition of functions, they introduced a relation called 'the universal relation' and suggested studying the composition of universal relations. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2018
Počet záznamů: 1