Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAlmost Optimal Pseudorandom Generators for Spherical Caps
97
0
0.0
(
0
)
Added by
Pravesh Kothari
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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.
We show that the rank of a depth-3 circuit (over any field) that is simple, minimal and zero is at most k^3log d. The previous best rank bound known was 2^{O(k^2)}(log d)^{k-2} by Dvir and Shpilka (STOC 2005). This almost resolves the rank question first posed by Dvir and Shpilka (as we also provide a simple and minimal identity of rank Omega(klog d)). Our rank bound significantly improves (dependence on k exponentially reduced) the best known deterministic black-box identity tests for depth-3 circuits by Karnin and Shpilka (CCC 2008). Our techniques also shed light on the factorization pattern of nonzero depth-3 circuits, most strikingly: the rank of linear factors of a simple, minimal and nonzero depth-3 circuit (over any field) is at most k^3log d. The novel feature of this work is a new notion of maps between sets of linear forms, called ideal matchings, used to study depth-3 circuits. We prove interesting structural results about depth-3 identities using these techniques. We believe that these can lead to the goal of a deterministic polynomial time identity test for these circuits.
The information geometry of the 2-manifold of gamma probability density functions provides a framework in which pseudorandom number generators may be evaluated using a neighbourhood of the curve of exponential density functions. The process is illustrated using the pseudorandom number generator in Mathematica. This methodology may be useful to add to the current family of test procedures in real applications to finite sampling data.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
