Počet záznamů: 1  

A composition theorem for randomized query complexity via Max-conflict complexity

  1. 1.
    SYSNO ASEP0507748
    Druh ASEPC - Konferenční příspěvek (mezinárodní konf.)
    Zařazení RIVD - Článek ve sborníku
    NázevA composition theorem for randomized query complexity via Max-conflict complexity
    Tvůrce(i) Gavinsky, Dmitry (MU-W) RID, SAI, ORCID
    Lee, T. (AU)
    Santha, M. (SG)
    Sanyal, S. (IN)
    Číslo článku64
    Zdroj.dok.46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). - Dagstuhl : Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2019 / Baier Ch. ; Chatzigiannakis I. ; Flocchini P. ; Leonardi S. - ISSN 1868-8969 - ISBN 978-3-95977-109-2
    Poč.str.13 s.
    Forma vydáníTištěná - P
    Akce46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
    Datum konání08.07.2019 - 12.07.2019
    Místo konáníPatras
    ZeměGR - Řecko
    Typ akceWRD
    Jazyk dok.eng - angličtina
    Země vyd.DE - Německo
    Klíč. slovaquery complexity ; lower bounds
    Vědní obor RIVIN - Informatika
    Obor OECDComputer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
    CEPGX19-27871X GA ČR - Grantová agentura ČR
    Institucionální podporaMU-W - RVO:67985840
    EID SCOPUS85069200872
    DOI10.4230/LIPIcs.ICALP.2019.64
    AnotaceFor any relation f subseteq {0,1}^n x S and any partial Boolean function g:{0,1}^m -> {0,1,*}, we show that R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * sqrt{R_{1/3}(g)}) , where R_epsilon(*) stands for the bounded-error randomized query complexity with error at most epsilon, and f o g^n subseteq ({0,1}^m)^n x S denotes the composition of f with n instances of g. The new composition theorem is optimal, at least, for the general case of relational problems: A relation f_0 and a partial Boolean function g_0 are constructed, such that R_{4/9}(f_0) in Theta(sqrt n), R_{1/3}(g_0)in Theta(n) and R_{1/3}(f_0 o g_0^n) in Theta(n). The theorem is proved via introducing a new complexity measure, max-conflict complexity, denoted by bar{chi}(*). Its investigation shows that bar{chi}(g) in Omega(sqrt{R_{1/3}(g)}) for any partial Boolean function g and R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * bar{chi}(g)) for any relation f, which readily implies the composition statement. It is further shown that bar{chi}(g) is always at least as large as the sabotage complexity of g.
    PracovištěMatematický ústav
    KontaktJarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
    Rok sběru2020
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.