Jiří Šíma ; Stanislav Žák - A polynomial-time construction of a hitting set for read-once branching programs of width 3

fi:7043 - Fundamenta Informaticae, March 10, 2022, Volume 184, Issue 4
A polynomial-time construction of a hitting set for read-once branching programs of width 3

Authors: Jiří Šíma ; Stanislav Žák

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 $\varepsilon>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.


Volume: Volume 184, Issue 4
Published on: March 10, 2022
Accepted on: February 3, 2022
Submitted on: January 5, 2021
Keywords: Computer Science - Computational Complexity


Share

Consultation statistics

This page has been seen 35 times.
This article's PDF has been downloaded 23 times.