skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Pseudorandomness for Unordered Branching Programs through Local Monotonicity
We present an explicit pseudorandom generator with seed length tildeO((log n)w+1) for read-once, 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 read-once, 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
Award ID(s):
1749810
PAR ID:
10079983
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
Proceedings of the annual ACM Symposium on Theory of Computing
ISSN:
0737-8017
Page Range / eLocation ID:
363-375
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Etessami, Kousha; Feige, Uriel; Puppis, Gabriele (Ed.)
    We give the first pseudorandom generators with sub-linear seed length for the following variants of read-once branching programs (roBPs): 1) First, we show there is an explicit PRG of seed length O(log²(n/ε)log(n)) fooling unbounded-width unordered permutation branching programs with a single accept state, where n is the length of the program. Previously, [Lee-Pyne-Vadhan RANDOM 2022] gave a PRG with seed length Ω(n) for this class. For the ordered case, [Hoza-Pyne-Vadhan ITCS 2021] gave a PRG with seed length Õ(log n ⋅ log 1/ε). 2) Second, we show there is an explicit PRG fooling unbounded-width unordered regular branching programs with a single accept state with seed length Õ(√{n ⋅ log 1/ε} log 1/ε). Previously, no non-trivial PRG (with seed length less than n) was known for this class (even in the ordered setting). For the ordered case, [Bogdanov-Hoza-Prakriya-Pyne 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 non-trivial seed length is known for this class. We remark that there are some functions computable by constant-width adaptive branching programs but not by sub-exponential-width unordered branching programs. In terms of techniques, we indeed show that the Forbes-Kelley PRG (with the right parameters) from [Forbes-Kelley FOCS 2018] already fools all variants of roBPs above. Our proof adds several new ideas to the original analysis of Forbes-Kelly, and we believe it further demonstrates the versatility of the Forbes-Kelley PRG. 
    more » « less
  2. ; ; (, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023)
    We give new upper and lower bounds on the power of several restricted classes of arbitrary-order read-once branching programs (ROBPs) and standard-order ROBPs (SOBPs) that have received significant attention in the literature on pseudorandomness for space-bounded computation. - Regular SOBPs of length n and width ⌊w(n+1)/2⌋ can exactly simulate general SOBPs of length n and width w, and moreover an n/2-o(n) blow-up in width is necessary for such a simulation. Our result extends and simplifies prior average-case simulations (Reingold, Trevisan, and Vadhan (STOC 2006), Bogdanov, Hoza, Prakriya, and Pyne (CCC 2022)), in particular implying that weighted pseudorandom generators (Braverman, Cohen, and Garg (SICOMP 2020)) for regular SOBPs of width poly(n) or larger automatically extend to general SOBPs. Furthermore, our simulation also extends to general (even read-many) oblivious branching programs. - There exist natural functions computable by regular SOBPs of constant width that are average-case hard for permutation SOBPs of exponential width. Indeed, we show that Inner-Product mod 2 is average-case hard for arbitrary-order permutation ROBPs of exponential width. - There exist functions computable by constant-width arbitrary-order permutation ROBPs that are worst-case hard for exponential-width SOBPs. - Read-twice permutation branching programs of subexponential width can simulate polynomial-width arbitrary-order ROBPs. 
    more » « less
  3. ; (, Leibniz international proceedings in informatics)
    Wootters, Mary; Sanita, Laura (Ed.)
    The orbit of an n-variate polynomial f(x) over a field 𝔽 is the set {f(Ax+b) ∣ A ∈ GL(n, 𝔽) and b ∈ 𝔽ⁿ}, and the orbit of a polynomial class is the union of orbits of all the polynomials in it. In this paper, we give improved constructions of hitting-sets for the orbit of read-once oblivious algebraic branching programs (ROABPs) and a related model. Over fields with characteristic zero or greater than d, we construct a hitting set of size (ndw)^{O(w²log n⋅ min{w², dlog w})} for the orbit of ROABPs in unknown variable order where d is the individual degree and w is the width of ROABPs. We also give a hitting set of size (ndw)^{O(min{w²,dlog w})} for the orbit of polynomials computed by w-width ROABPs in any variable order. Our hitting sets improve upon the results of Saha and Thankey [Chandan Saha and Bhargav Thankey, 2021] who gave an (ndw)^{O(dlog w)} size hitting set for the orbit of commutative ROABPs (a subclass of any-order ROABPs) and (nw)^{O(w⁶log n)} size hitting set for the orbit of multilinear ROABPs. Designing better hitting sets in large individual degree regime, for instance d > n, was asked as an open problem by [Chandan Saha and Bhargav Thankey, 2021] and this work solves it in small width setting. We prove some new rank concentration results by establishing low-cone concentration for the polynomials over vector spaces, and they strengthen some previously known low-support based rank concentrations shown in [Michael A. Forbes et al., 2013]. These new low-cone concentration results are crucial in our hitting set construction, and may be of independent interest. To the best of our knowledge, this is the first time when low-cone rank concentration has been used for designing hitting sets. 
    more » « less
  4. ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Guruswami, Venkatesan (Ed.)
    In a recent work, Chen, Hoza, Lyu, Tal and Wu (FOCS 2023) showed an improved error reduction framework for the derandomization of regular read-once branching programs (ROBPs). Their result is based on a clever modification to the inverse Laplacian perspective of space-bounded derandomization, which was originally introduced by Ahmadinejad, Kelner, Murtagh, Peebles, Sidford and Vadhan (FOCS 2020). In this work, we give an alternative error reduction framework for regular ROBPs. Our new framework is based on a binary recursive formula from the work of Chattopadhyay and Liao (CCC 2020), that they used to construct weighted pseudorandom generators (WPRGs) for general ROBPs. Based on our new error reduction framework, we give alternative proofs to the following results for regular ROBPs of length n and width w, both of which were proved in the work of Chen et al. using their error reduction: - There is a WPRG with error ε that has seed length Õ(log(n)(√{log(1/ε)}+log(w))+log(1/ε)). - There is a (non-black-box) deterministic algorithm which estimates the expectation of any such program within error ±ε with space complexity Õ(log(nw)⋅log log(1/ε)). This was first proved in the work of Ahmadinejad et al., but the proof by Chen et al. is simpler. Because of the binary recursive nature of our new framework, both of our proofs are based on a straightforward induction that is arguably simpler than the Laplacian-based proof in the work of Chen et al. In fact, because of its simplicity, our proof of the second result directly gives a slightly stronger claim: our algorithm computes a ε-singular value approximation (a notion of approximation introduced in a recent work by Ahmadinejad, Peebles, Pyne, Sidford and Vadhan (FOCS 2023)) of the random walk matrix of the given ROBP in space Õ(log(nw)⋅log log(1/ε)). It is not clear how to get this stronger result from the previous proofs. 
    more » « less
  5. ; ; (, Journal of the ACM)
    One powerful theme in complexity theory and pseudorandomness in the past few decades has been the use of lower bounds to give pseudorandom generators (PRGs). However, the general results using this hardness vs. randomness paradigm suffer from a quantitative loss in parameters, and hence do not give nontrivial implications for models where we don't know super-polynomial lower bounds but do know lower bounds of a fixed polynomial. We show that when such lower bounds are proved using random restrictions, we can construct PRGs that are essentially best possible without in turn improving the lower bounds. More specifically, say that a circuit family has shrinkage exponent Gamma if a random restriction leaving a p fraction of variables unset shrinks the size of any circuit in the family by a factor of p^{Gamma + o(1)}. Our PRG uses a seed of length s^{1/(Gamma + 1) + o(1)} to fool circuits in the family of size s. By using this generic construction, we get PRGs with polynomially small error for the following classes of circuits of size s and with the following seed lengths: 1. For de Morgan formulas, seed length s^{1/3+o(1)}; 2. For formulas over an arbitrary basis, seed length s^{1/2+o(1)}; 3. For read-once de Morgan formulas, seed length s^{.234...}; 4. For branching programs of size s, seed length s^{1/2+o(1)}. The previous best PRGs known for these classes used seeds of length bigger than n/2 to output n bits, and worked only when the size s=O(n). 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email