Počet záznamů: 1  

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

  1. 1.
    0434460 - MÚ 2015 RIV US eng C - Konferenční příspěvek (zahraniční konf.)
    Gavinsky, Dmitry - Meir, O. - Weinstein, O. - Wigderson, A.
    Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture.
    Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014). New York: ACM, 2014 - (Shmoys, D.), s. 213-222. ISBN 978-1-4503-2710-7.
    [STOC 2014. Symposium on Theory of Computing /46./. New York (US), 31.05.2014-03.06.2014]
    Grant CEP: GA ČR GBP202/12/G061
    Institucionální podpora: RVO:67985840
    Klíčová slova: formula lower bounds * information complexity * composition conjecture
    Kód oboru RIV: BA - Obecná matematika
    http://dl.acm.org/citation.cfm?id=2591856&dl=ACM&coll=DL&CFID=454065209&CFTOKEN=54114198

    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.
    Trvalý link: http://hdl.handle.net/11104/0238543

     
    Název souboruStaženoVelikostKomentářVerzePřístup
    Gavinsky2.pdf9415.2 KBVydavatelský postprintvyžádat
     
Počet záznamů: 1  

  Tyto stránky využívají soubory cookies, které usnadňují jejich prohlížení. Další informace o tom jak používáme cookies.