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

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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).

Název v anglickém jazyce

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

Popis výsledku anglicky

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).

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2011

Kód důvěrnosti údajů

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

Název statě ve sborníku

Computer Science - Theory and Applications

ISBN

978-3-642-20711-2

ISSN

—

e-ISSN

—

Počet stran výsledku

14

Strana od-do

120-133

Název nakladatele

Springer

Místo vydání

Berlin

Místo konání akce

St. Petersburg

Datum konání akce

14. 6. 2011

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—