The classic Impagliazzo–Nisan–Wigderson (INW) pseudorandom generator (PRG) (STOC ‘94) for space-bounded computation uses a seed of length
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
Abstract to fool ordered branching programs of length$$O(\log n \cdot \log (nw/\varepsilon )+\log d)$$ 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 $$ permutation branching programs or the more generalregular branching programs, improving the dependence on the length$$O(\log ^2 n)$$ n to or$$O(\log n)$$ . 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)$$ . In this paper, we prove that any “spectral analysis” of the INW generator requires seed length$$O(\log (nwd/\varepsilon ))$$ 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}$$ 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 $$ except for a gap between their$$d=2$$ term and our$$O\left( \log n \cdot \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 constant-width ($$\Omega \left( \log n \cdot \log \log \min \{n,d\}\right) $$ ) permutation branching programs of alphabet size$$w=O(1)$$ to within a constant factor. To fool permutation branching programs in the measure of$$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) $$ n ( ), matching the recent upper bound of Hoza–Pyne–Vadhan (ITCS 2021) to within a constant factor.$$w=n^{\Omega (1)}$$ -
We introduce a novel family of expander-based error correcting codes. These codes can be sampled with randomness linear in the block-length, and achieve list decoding capacity (among other local properties). Our expander-based codes can be made starting from any family of sufficiently low-bias codes, and as a consequence, we give the first construction of a family of algebraic codes that can be sampled with linear randomness and achieve list-decoding capacity. We achieve this by introducing the notion of a pseudorandom puncturing of a code, where we select n indices of a base code C ⊂ 𝔽_q^m in a correlated fashion. Concretely, whereas a random linear code (i.e. a truly random puncturing of the Hadamard code) requires O(n log(m)) random bits to sample, we sample a pseudorandom linear code with O(n + log (m)) random bits by instantiating our pseudorandom puncturing as a length n random walk on an exapnder graph on [m]. In particular, we extend a result of Guruswami and Mosheiff (FOCS 2022) and show that a pseudorandom puncturing of a small-bias code satisfies the same local properties as a random linear code with high probability. As a further application of our techniques, we also show that pseudorandom puncturings of Reed-Solomon codes are list-recoverable beyond the Johnson bound, extending a result of Lund and Potukuchi (RANDOM 2020). We do this by instead analyzing properties of codes with large distance, and show that pseudorandom puncturings still work well in this regime.more » « less
-
Let L be a language that can be decided in linear space and let ϵ>0 be any constant. Let A be the exponential hardness assumption that for every n, membership in L for inputs of length n cannot be decided by circuits of size smaller than 2ϵn. We prove that for every function f:{0,1}∗→{0,1}, computable by a randomized logspace algorithm R, there exists a deterministic logspace algorithm D (attempting to compute f), such that on every input x of length n, the algorithm D outputs one of the following:1)The correct value f(x).2)The string: “I am unable to compute f(x) because the hardness assumption A is false”, followed by a (provenly correct) circuit of size smaller than 2ϵn′ for membership in L for inputs of length n′, for some n′=Θ(logn); that is, a circuit that refutes A. Moreover, D is explicitly constructed, given R.We note that previous works on the hardness-versus-randomness paradigm give derandomized algorithms that rely blindly on the hardness assumption. If the hardness assumption is false, the algorithms may output incorrect values, and thus a user cannot trust that an output given by the algorithm is correct. Instead, our algorithm D verifies the computation so that it never outputs an incorrect value. Thus, if D outputs a value for f(x), that value is certified to be correct. Moreover, if D does not output a value for f(x), it alerts that the hardness assumption was found to be false, and refutes the assumption.Our next result is a universal derandomizer for BPL (the class of problems solvable by bounded-error randomized logspace algorithms) 1 : We give a deterministic algorithm U that takes as an input a randomized logspace algorithm R and an input x and simulates the computation of R on x, deteriministically. Under the widely believed assumption BPL=L, the space ...more » « less
-
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
-
A spanner of a graph is a subgraph that preserves lengths of shortest paths up to a multiplicative distortion. For every k, a spanner with size O(n^{1+1/k}) and stretch (2k+1) can be constructed by a simple centralized greedy algorithm, and this is tight assuming Erdős girth conjecture. In this paper we study the problem of constructing spanners in a local manner, specifically in the Local Computation Model proposed by Rubinfeld et al. (ICS 2011). We provide a randomized Local Computation Agorithm (LCA) for constructing (2r-1)-spanners with Õ(n^{1+1/r}) edges and probe complexity of Õ(n^{1-1/r}) for r ∈ {2,3}, where n denotes the number of vertices in the input graph. Up to polylogarithmic factors, in both cases, the stretch factor is optimal (for the respective number of edges). In addition, our probe complexity for r = 2, i.e., for constructing a 3-spanner, is optimal up to polylogarithmic factors. Our result improves over the probe complexity of Parter et al. (ITCS 2019) that is Õ(n^{1-1/2r}) for r ∈ {2,3}. Both our algorithms and the algorithms of Parter et al. use a combination of neighbor-probes and pair-probes in the above-mentioned LCAs. For general k ≥ 1, we provide an LCA for constructing O(k²)-spanners with Õ(n^{1+1/k}) edges using O(n^{2/3}Δ²) neighbor-probes, improving over the Õ(n^{2/3}Δ⁴) algorithm of Parter et al. By developing a new randomized LCA for graph decomposition, we further improve the probe complexity of the latter task to be O(n^{2/3-(1.5-α)/k}Δ²), for any constant α > 0. This latter LCA may be of independent interest.more » « less