Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFractional Pseudorandom Generators from Any Fourier Level
140
0
0.0
(
0
)
Added by
Abhishek Shetty
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We prove new results on the polarizing random walk framework introduced in recent works of Chattopadhyay {et al.} [CHHL19,CHLT19] that exploit $L_1$ Fourier tail bounds for classes of Boolean functions to construct pseudorandom generators (PRGs). We show that given a bound on the $k$-th level of the Fourier spectrum, one can construct a PRG with a seed length whose quality scales with $k$. This interpolates previous works, which either require Fourier bounds on all levels [CHHL19], or have polynomial dependence on the error parameter in the seed length [CHLT10], and thus answers an open question in [CHLT19]. As an example, we show that for polynomial error, Fourier bounds on the first $O(log n)$ levels is sufficient to recover the seed length in [CHHL19], which requires bounds on the entire tail. We obtain our results by an alternate analysis of fractional PRGs using Taylors theorem and bounding the degree-$k$ Lagrange remainder term using multilinearity and random restrictions. Interestingly, our analysis relies only on the emph{level-k unsigned Fourier sum}, which is potentially a much smaller quantity than the $L_1$ notion in previous works. By generalizing a connection established in [CHH+20], we give a new reduction from constructing PRGs to proving correlation bounds. Finally, using these improvements we show how to obtain a PRG for $mathbb{F}_2$ polynomials with seed length close to the state-of-the-art construction due to Viola [Vio09], which was not known to be possible using this framework.
rate research
Read More
Halfspaces or linear threshold functions are widely studied in complexity theory, learning theory and algorithm design. In this work we study the natural problem of constructing pseudorandom generators (PRGs) for halfspaces over the sphere, aka spherical caps, which besides being interesting and basic geometric objects, also arise frequently in the analysis of various randomized algorithms (e.g., randomized rounding). We give an explicit PRG which fools spherical caps within error $epsilon$ and has an almost optimal seed-length of $O(log n + log(1/epsilon) cdot loglog(1/epsilon))$. For an inverse-polynomially growing error $epsilon$, our generator has a seed-length optimal up to a factor of $O( log log {(n)})$. The most efficient PRG previously known (due to Kane, 2012) requires a seed-length of $Omega(log^{3/2}{(n)})$ in this setting. We also obtain similar constructions to fool halfspaces with respect to the Gaussian distribution. Our construction and analysis are significantly different from previous works on PRGs for halfspaces and build on the iterative dimension reduction ideas of Kane et. al. (2011) and Celis et. al. (2013), the emph{classical moment problem} from probability theory and explicit constructions of emph{orthogonal designs} based on the seminal work of Bourgain and Gamburd (2011) on expansion in Lie groups.
We construct pseudorandom generators of seed length $tilde{O}(log(n)cdot log(1/epsilon))$ that $epsilon$-fool ordered read-once branching programs (ROBPs) of width $3$ and length $n$. For unordered ROBPs, we construct pseudorandom generators with seed length $tilde{O}(log(n) cdot mathrm{poly}(1/epsilon))$. This is the first improvement for pseudorandom generators fooling width $3$ ROBPs since the work of Nisan [Combinatorica, 1992]. Our constructions are based on the `iterated milder restrictions approach of Gopalan et al. [FOCS, 2012] (which further extends the Ajtai-Wigderson framework [FOCS, 1985]), combined with the INW-generator [STOC, 1994] at the last step (as analyzed by Braverman et al. [SICOMP, 2014]). For the unordered case, we combine iterated milder restrictions with the generator of Chattopadhyay et al. [CCC, 2018]. Two conceptual ideas that play an important role in our analysis are: (1) A relabeling technique allowing us to analyze a relabeled version of the given branching program, which turns out to be much easier. (2) Treating the number of colliding layers in a branching program as a progress measure and showing that it reduces significantly under pseudorandom restrictions. In addition, we achieve nearly optimal seed-length $tilde{O}(log(n/epsilon))$ for the classes of: (1) read-once polynomials on $n$ variables, (2) locally-monotone ROBPs of length $n$ and width $3$ (generalizing read-once CNFs and DNFs), and (3) constant-width ROBPs of length $n$ having a layer of width $2$ in every consecutive $mathrm{poly}log(n)$ layers.
Linear pseudorandom number generators are very popular due to their high speed, to the ease with which generators with a sizable state space can be created, and to their provable theoretical properties. However, they suffer from linear artifacts which show as failures in linearity-related statistical tests such as the binary-rank and the linear-complexity test. In this paper, we give three new contributions. First, we introduce two new linear transformations that have been handcrafted to have good statistical properties and at the same time to be programmable very efficiently on superscalar processors, or even directly in hardware. Then, we describe a new test for Hamming-weight dependencies that is able to discover subtle, previously unknown biases in existing generators (in particular, in linear ones). Finally, we describe a number of scramblers, that is, nonlinear functions applied to the state array that reduce or delete the linear artifacts, and propose combinations of linear transformations and scramblers that give extremely fast pseudorandom generators of high quality. A novelty in our approach is that we use ideas from the theory of filtered linear-feedback shift register to prove some properties of our scramblers, rather than relying purely on heuristics. In the end, we provide simple, extremely fast generators that use a few hundred bits of memory, have provable properties and pass very strong statistical tests.
We show that quantum algorithms of time $T$ and space $Sge log T$ with unitary operations and intermediate measurements can be simulated by quantum algorithms of time $T cdot mathrm{poly} (S)$ and space $ {O}(Scdot log T)$ with unitary operations and without intermediate measurements. The best results prior to this work required either $Omega(T)$ space (by the deferred measurement principle) or $mathrm{poly}(2^S)$ time [FR21,GRZ21]. Our result is thus a time-efficient and space-efficient simulation of algorithms with unitary operations and intermediate measurements by algorithms with unitary operations and without intermediate measurements. To prove our result, we study pseudorandom generators for quantum space-bounded algorithms. We show that (an instance of) the INW pseudorandom generator for classical space-bounded algorithms [INW94] also fools quantum space-bounded algorithms. More precisely, we show that for quantum space-bounded algorithms that have access to a read-once tape consisting of random bits, the final state of the algorithm when the random bits are drawn from the uniform distribution is nearly identical to the final state when the random bits are drawn using the INW pseudorandom generator. This result applies to general quantum algorithms which can apply unitary operations, perform intermediate measurements and reset qubits.
We generalize the deterministic simulation theorem of Raz and McKenzie [RM99], to any gadget which satisfies certain hitting property. We prove that inner-product and gap-Hamming satisfy this property, and as a corollary we obtain deterministic simulation theorem for these gadgets, where the gadgets input-size is logarithmic in the input-size of the outer function. This answers an open question posed by G{o}{o}s, Pitassi and Watson [GPW15]. Our result also implies the previous results for the Indexing gadget, with better parameters than was previously known. A preliminary version of the results obtained in this work appeared in [CKL+17].
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
