This content will become publicly available on September 11, 2024
 Award ID(s):
 2310818
 NSFPAR ID:
 10494247
 Publisher / Repository:
 Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023
 Date Published:
 Journal Name:
 Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023
 Page Range / eLocation ID:
 44:144:22
 Format(s):
 Medium: X
 Location:
 Atlanta, Georgia
 Sponsoring Org:
 National Science Foundation
More Like this

Etessami, Kousha ; Feige, Uriel ; Puppis, Gabriele (Ed.)We give the first pseudorandom generators with sublinear seed length for the following variants of readonce branching programs (roBPs): 1) First, we show there is an explicit PRG of seed length O(log²(n/ε)log(n)) fooling unboundedwidth unordered permutation branching programs with a single accept state, where n is the length of the program. Previously, [LeePyneVadhan RANDOM 2022] gave a PRG with seed length Ω(n) for this class. For the ordered case, [HozaPyneVadhan ITCS 2021] gave a PRG with seed length Õ(log n ⋅ log 1/ε). 2) Second, we show there is an explicit PRG fooling unboundedwidth unordered regular branching programs with a single accept state with seed length Õ(√{n ⋅ log 1/ε} log 1/ε). Previously, no nontrivial PRG (with seed length less than n) was known for this class (even in the ordered setting). For the ordered case, [BogdanovHozaPrakriyaPyne CCC 2022] gave an HSG with seed length Õ(log n ⋅ log 1/ε). 3) Third, we show there is an explicit PRG fooling width w adaptive branching programs with seed length O(log n ⋅ log² (nw/ε)). Here, the branching program can choose an input bit to read depending on its current state, while it is guaranteed that on any input x ∈ {0,1}ⁿ, the branching program reads each input bit exactly once. Previously, no PRG with a nontrivial seed length is known for this class. We remark that there are some functions computable by constantwidth adaptive branching programs but not by subexponentialwidth unordered branching programs. In terms of techniques, we indeed show that the ForbesKelley PRG (with the right parameters) from [ForbesKelley FOCS 2018] already fools all variants of roBPs above. Our proof adds several new ideas to the original analysis of ForbesKelly, and we believe it further demonstrates the versatility of the ForbesKelley PRG.more » « less

We present an explicit pseudorandom generator with seed length tildeO((log n)w+1) for readonce, oblivious, width w branching programs that can read their input bits in any order. This improves upon the work of Impaggliazzo, Meka and Zuckerman (FOCS'12) where they required seed length n^{1/2+o(1)}. A central ingredient in our work is the following bound that we prove on the Fourier spectrum of branching programs. For any width w readonce, oblivious branching program B : {0, 1}^n > {0, 1}, any k in {1,2,...,n}, Sum_{S subseteq [n];S=k} \hat{B}(S) leq O(log n)^{wk}. This settles a conjecture posed by Reingold, Steinke, and Vadhan (RANDOM'13). Our analysis crucially uses a notion of local monotonicity on the edge labeling of the branching program. We carry critical parts of our proof under the assumption of local monotonicity and show how to deduce our results for unrestricted branching programs.more » « less

TaShma, Amnon (Ed.)In a recent work, Gryaznov, Pudlák and Talebanfard (CCC '22) introduced a linear variant of readonce branching programs, with motivations from circuit and proof complexity. Such a readonce linear branching program is a branching program where each node is allowed to make 𝔽₂linear queries, and is readonce in the sense that the queries on each path is linearly independent. As their main result, they constructed an explicit function with averagecase complexity 2^{n/3o(n)} against a slightly restricted model, which they call strongly readonce linear branching programs. The main tool in their lower bound result is a new type of extractor, called directional affine extractors, that they introduced. Our main result is an explicit function with 2^{no(n)} averagecase complexity against the strongly readonce linear branching program model, which is almost optimal. This result is based on a new connection from this problem to sumset extractors, which is a randomness extractor model introduced by Chattopadhyay and Li (STOC '16) as a generalization of many other wellstudied models including twosource extractors, affine extractors and smallspace extractors. With this new connection, our lower bound naturally follows from a recent construction of sumset extractors by Chattopadhyay and Liao (STOC '22). In addition, we show that directional affine extractors imply sumset extractors in a restricted setting. We observe that such restricted sumset sources are enough to derive lower bounds, and obtain an arguably more modular proof of the lower bound by Gryaznov, Pudlák and Talebanfard. We also initiate a study of pseudorandomness against linear branching programs. Our main result here is a hitting set generator construction against regular linear branching programs with constant width. We derive this result based on a connection to Kakeya sets over finite fields.more » « less

Abstract The classic Impagliazzo–Nisan–Wigderson (INW) pseudorandom generator (PRG) (STOC ‘94) for spacebounded computation uses a seed of length
to fool ordered branching programs of length$$O(\log n \cdot \log (nw/\varepsilon )+\log d)$$ $O(logn\xb7log(nw/\epsilon )+logd)$n , widthw , and alphabet sized to within error . A series of works have shown that the analysis of the INW generator can be improved for the class of$$\varepsilon $$ $\epsilon $permutation branching programs or the more generalregular branching programs, improving the dependence on the length$$O(\log ^2 n)$$ $O\left({log}^{2}n\right)$n to or$$O(\log n)$$ $O(logn)$ . However, when also considering the dependence on the other parameters, these analyses still fall short of the optimal PRG seed length$${\tilde{O}}(\log n)$$ $\stackrel{~}{O}(logn)$ . In this paper, we prove that any “spectral analysis” of the INW generator requires seed length$$O(\log (nwd/\varepsilon ))$$ $O(log(nwd/\epsilon \left)\right)$ to fool ordered permutation branching programs of length$$\begin{aligned} \Omega \left( \log n\cdot \log \log \left( \min \{n,d\}\right) +\log n\cdot \log \left( w/\varepsilon \right) +\log d\right) \end{aligned}$$ $\begin{array}{c}\Omega \left(log,n,\xb7,log,log,\left(min,\{,n,,,d,\}\right),+,log,n,\xb7,log,\left(w,/,\epsilon \right),+,log,d\right)\end{array}$n , widthw , and alphabet sized to within error . By “spectral analysis” we mean an analysis of the INW generator that relies only on the spectral expansion of the graphs used to construct the generator; this encompasses all prior analyses of the INW generator. Our lower bound matches the upper bound of Braverman–Rao–Raz–Yehudayoff (FOCS 2010, SICOMP 2014) for regular branching programs of alphabet size$$\varepsilon $$ $\epsilon $ except for a gap between their$$d=2$$ $d=2$ term and our$$O\left( \log n \cdot \log \log n\right) $$ $O\left(log,n,\xb7,log,log,n\right)$ term. It also matches the upper bounds of Koucký–Nimbhorkar–Pudlák (STOC 2011), De (CCC 2011), and Steinke (ECCC 2012) for constantwidth ($$\Omega \left( \log n \cdot \log \log \min \{n,d\}\right) $$ $\Omega \left(log,n,\xb7,log,log,min,\{,n,,,d,\}\right)$ ) permutation branching programs of alphabet size$$w=O(1)$$ $w=O\left(1\right)$ to within a constant factor. To fool permutation branching programs in the measure of$$d=2$$ $d=2$spectral norm , we prove that any spectral analysis of the INW generator requires a seed of length when the width is at least polynomial in$$\Omega \left( \log n\cdot \log \log n+\log n\cdot \log (1/\varepsilon )\right) $$ $\Omega \left(log,n,\xb7,log,log,n,+,log,n,\xb7,log,(,1,/,\epsilon ,)\right)$n ( ), matching the recent upper bound of Hoza–Pyne–Vadhan (ITCS 2021) to within a constant factor.$$w=n^{\Omega (1)}$$ $w={n}^{\Omega \left(1\right)}$ 
We give a deterministic whitebox algorithm to estimate the expectation of a readonce branching program of length n and width w in space Õ(logn+√logn·logw). In particular, we obtain an almost optimal space Õ(logn) derandomization of programs up to width w=2√logn. Previously, the best known space complexity for this problem was O(min{logn· logw,log3/2n+√logn· logw}) via the classic algorithms of Savitch (JCSS 1970) and Saks and Zhou (JCSS 1999), which only achieve space Õ(logn) for w=polylog(n). We prove this result by showing that a variant of the SaksZhou algorithm developed by Cohen, Doron, and Sberlo (ECCC 2022) still works without executing one of the steps in the algorithm, the socalled random shift step. This allows us to extend their algorithm from computing the nth power of a w× w stochastic matrix to multiplying n distinct w× w stochastic matrices with no degradation in space consumption. In the regime where w≥ n, we also show that our approach can achieve parameters matching those of the original SaksZhou algorithm (with no loglog factors). Finally, we show that for w≤ 2√logn, an algorithm even simpler than our algorithm and that of Saks and Zhou achieves space O(log3/2 n).more » « less