Počet záznamů: 1

Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs

  1. 1.
    0360403 - UIVT-O 2012 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
    Šíma, Jiří - Žák, Stanislav
    Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs.
    Computer Science - Theory and Applications. Berlin: Springer, 2011 - (Kulikov, A.; Vereshchagin, N.), s. 120-133. Lecture Notes in Computer Science, 6651. ISBN 978-3-642-20711-2. ISSN 0302-9743.
    [CSR 2011. International Computer Science Symposium in Russia /6./. St. Petersburg (RU), 14.06.2011-18.06.2011]
    Grant CEP: GA ČR GAP202/10/1333; GA MŠk(CZ) 1M0545
    Výzkumný záměr: CEZ:AV0Z10300504
    Klíčová slova: almost k-wise independent set * hitting set * read-once branching programs * derandomization * bounded width
    Kód oboru RIV: IN - Informatika

    Recently, an interest in constructing pseudorandom or hitting set generators for restricted branching programs has increased, which is motivated by the fundamental problem of derandomizing space bounded computations. Such constructions have been known only in the case of width 2 and in very restricted cases of bounded width. In our previous work, we have introduced a so-called richness condition which is, in a certain sense, sufficient for a set to be a hitting set for read-once branching programs of width 3. In this paper, we prove that, for a suitable constant C, any almost (C log n)-wise independent set satisfies this richness condition. Hence, we achieve an explicit polynomial time construction of a hitting set for read-once branching programs of width~3 with the acceptance probability greater than 12/13 by using the result due to Alon et al. (1992).
    Trvalý link: http://hdl.handle.net/11104/0197967
    Název souboruStaženoVelikostKomentářVerzePřístup
    0360403.pdf0622.5 KBAutorský preprintpovolen