A Polynomial-time Construction of a Hitting Set for Read-once Branching Programs of Width 3

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F21%3A00367350" target="_blank" >RIV/67985807:_____/21:00367350 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.3233/FI-2021-2101" target="_blank" >http://dx.doi.org/10.3233/FI-2021-2101</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.3233/FI-2021-2101" target="_blank" >10.3233/FI-2021-2101</a>

Result language

angličtina

Original language name

A Polynomial-time Construction of a Hitting Set for Read-once Branching Programs of Width 3

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

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2021

Confidentiality

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

Name of the periodical

Fundamenta Informaticae

ISSN

0169-2968

e-ISSN

1875-8681

Volume of the periodical

184

Issue of the periodical within the volume

4

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

48

Pages from-to

307-354

UT code for WoS article

000768542000003

EID of the result in the Scopus database

2-s2.0-85127188809