Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-225 | 3rd October 2026 22:37

Beyond Width-3: Better Hitting Set Generators for Width-4 Read-Once Branching Programs

RSS-Feed




TR26-225
Authors: Gonen Krak
Publication: 4th October 2026 01:28
Downloads: 20
Keywords: 


Abstract:

We construct an explicit hitting set generator (HSG) for ordered read-once branching programs of width 4. For every length $n$ and every $\varepsilon \in (0,1)$, every width-4 length-$n$ program that accepts more than an $\varepsilon$ fraction of its inputs accepts at least one output of the generator, and the seed length is $$O\big((\log n)^{3/2} \cdot \sqrt{\log\log n} \cdot (1 + \log(1/\varepsilon))\big).$$ For constant $\varepsilon$ this is $O(\log^{3/2} n \cdot \sqrt{\log\log n})$. More generally, it is $o(\log^2 n)$ whenever $\varepsilon \ge 2^{-o(\sqrt{\log n/\log\log n})}$. This is the first explicit generator for width 4 that improves on the $O(\log^2 n)$ seed length of Nisan's generator (Combinatorica 1992).

Our construction first reduces the hitting problem for width-4 programs to the hitting problem for programs with three live states and one rejecting state, following Doron and Hoza (RANDOM 2025). It then simplifies these programs by rounds of pseudorandom restrictions, and hits the simplified programs with a small-bias string that is modified in a small number of positions.



ISSN 1433-8092 | Imprint