Bogdanov, Andrej ;
Hoza, William M. ;
Prakriya, Gautam ;
Pyne, Edward
Hitting Sets for Regular Branching Programs
Abstract
We construct improved hitting set generators (HSGs) for ordered (readonce) regular branching programs in two parameter regimes. First, we construct an explicit εHSG for unboundedwidth regular branching programs with a single accept state with seed length Õ(log n ⋅ log(1/ε)), where n is the length of the program. Second, we construct an explicit εHSG for widthw lengthn regular branching programs with seed length Õ(log n ⋅ (√{log(1/ε)} + log w) + log(1/ε)). For context, the "baseline" in this area is the pseudorandom generator (PRG) by Nisan (Combinatorica 1992), which fools ordered (possibly nonregular) branching programs with seed length O(log(wn/ε) ⋅ log n). For regular programs, the stateoftheart PRG, by Braverman, Rao, Raz, and Yehudayoff (FOCS 2010, SICOMP 2014), has seed length Õ(log(w/ε) ⋅ log n), which beats Nisan’s seed length when log(w/ε) = o(log n). Taken together, our two new constructions beat Nisan’s seed length in all parameter regimes except when log w and log(1/ε) are both Ω(log n) (for the construction of HSGs for regular branching programs with a single accept vertex).
Extending work by Reingold, Trevisan, and Vadhan (STOC 2006), we furthermore show that an explicit HSG for regular branching programs with a single accept vertex with seed length o(log² n) in the regime log w = Θ(log(1/ε)) = Θ(log n) would imply improved HSGs for general ordered branching programs, which would be a major breakthrough in derandomization. Pyne and Vadhan (CCC 2021) recently obtained such parameters for the special case of permutation branching programs.
BibTeX  Entry
@InProceedings{bogdanov_et_al:LIPIcs.CCC.2022.3,
author = {Bogdanov, Andrej and Hoza, William M. and Prakriya, Gautam and Pyne, Edward},
title = {{Hitting Sets for Regular Branching Programs}},
booktitle = {37th Computational Complexity Conference (CCC 2022)},
pages = {3:13:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772419},
ISSN = {18688969},
year = {2022},
volume = {234},
editor = {Lovett, Shachar},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16565},
URN = {urn:nbn:de:0030drops165658},
doi = {10.4230/LIPIcs.CCC.2022.3},
annote = {Keywords: Pseudorandomness, hitting set generators, spacebounded computation}
}
11.07.2022
Keywords: 

Pseudorandomness, hitting set generators, spacebounded computation 
Seminar: 

37th Computational Complexity Conference (CCC 2022)

Issue date: 

2022 
Date of publication: 

11.07.2022 