Počet záznamů: 1
Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs
- 1.
SYSNO ASEP 0360403 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV D - Článek ve sborníku Název Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs Tvůrce(i) Šíma, Jiří (UIVT-O) RID, SAI, ORCID
Žák, Stanislav (UIVT-O) SAI, RIDZdroj.dok. Computer Science - Theory and Applications. - Berlin : Springer, 2011 / Kulikov A. ; Vereshchagin N. - ISSN 0302-9743 - ISBN 978-3-642-20711-2 Rozsah stran s. 120-133 Poč.str. 14 s. Akce CSR 2011. International Computer Science Symposium in Russia /6./ Datum konání 14.06.2011-18.06.2011 Místo konání St. Petersburg Země RU - Rusko Typ akce WRD Jazyk dok. eng - angličtina Země vyd. DE - Německo Klíč. slova almost k-wise independent set ; hitting set ; read-once branching programs ; derandomization ; bounded width Vědní obor RIV IN - Informatika CEP GAP202/10/1333 GA ČR - Grantová agentura ČR 1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy CEZ AV0Z10300504 - UIVT-O (2005-2011) EID SCOPUS 79959304214 DOI 10.1007/978-3-642-20712-9_10 Anotace 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). Pracoviště Ústav informatiky Kontakt Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Rok sběru 2012
Počet záznamů: 1