Počet záznamů: 1
A Polynomial-Time Construction of a Hitting Set for Read-once Branching Programs of Width 3
- 1.
SYSNO ASEP 0367350 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 A Polynomial-Time Construction of a Hitting Set for Read-once Branching Programs of Width 3 Tvůrce(i) Šíma, Jiří (UIVT-O) RID, SAI, ORCID
Žák, Stanislav (UIVT-O) SAI, RIDZdroj.dok. Fundamenta Informaticae. - : IOS Press - ISSN 0169-2968
Roč. 184, č. 4 (2021), s. 307-354Poč.str. 48 s. Forma vydání Tištěná - P Jazyk dok. eng - angličtina Země vyd. NL - Nizozemsko Klíč. slova derandomization ; hitting set ; read-once branching programs ; bounded width ; almost k-wise independent set Vědní obor RIV IN - Informatika 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 GAP202/10/1333 GA ČR - Grantová agentura ČR Způsob publikování Omezený přístup Institucionální podpora UIVT-O - RVO:67985807 UT WOS 000768542000003 EID SCOPUS 85127188809 DOI https://doi.org/10.3233/FI-2021-2101 Anotace Recently, an interest in constructing pseudorandom or hitting set generators for restricted branching programs has increased, which is motivated by the fundamental issue 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 this paper, we characterize the hitting sets for read-once branching programs of width 3 by a so-called richness condition. Namely, we show that such sets hit the class of read-once conjunctions of DNF and CNF (i.e. the weak richness). Moreover, we prove that any rich set extended with all strings within Hamming distance of 3 is a hitting set for read-once branching programs of width 3. Then, we show that any almost O(log n)-wise independent set satisfies the richness condition. By using such a set due to Alon et al. (1992) our result provides an explicit polynomial-time construction of a hitting set for read-once branching programs of width 3 with acceptance probability epsilon>5/6. We announced this result at conferences more than ten years ago, including only proof sketches, which motivated a number of subsequent results on pseudorandom generators for restricted read-once branching programs. This paper contains our original detailed proof that has not been published yet. Pracoviště Ústav informatiky Kontakt Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Rok sběru 2022 Elektronická adresa http://dx.doi.org/10.3233/FI-2021-2101
Počet záznamů: 1