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

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F11%3A00360403" target="_blank" >RIV/67985807:_____/11:00360403 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-642-20712-9_10" target="_blank" >http://dx.doi.org/10.1007/978-3-642-20712-9_10</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-20712-9_10" target="_blank" >10.1007/978-3-642-20712-9_10</a>

Result language
angličtina
Original language name
Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs
Original language description
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 width3 with the acceptance probability greater than 12/13 by using the result due to Alon et al. (1992).
Czech name
—
Czech description
—

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2011
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)