
arXiv: 1506.04350
We present a new approach to constructing unconditional pseudorandom generators against classes of functions that involve computing a linear function of the inputs. We give an explicit construction of a pseudorandom generator that fools the discrete Fourier transforms of linear functions with seed-length that is nearly logarithmic (up to polyloglog factors) in the input size and the desired error parameter. Our result gives a single pseudorandom generator that fools several important classes of tests computable in logspace that have been considered in the literature, including halfspaces (over general domains), modular tests and combinatorial shapes. For all these classes, our generator is the first that achieves near logarithmic seed-length in both the input length and the error parameter. Getting such a seed-length is a natural challenge in its own right, which needs to be overcome in order to derandomize RL - a central question in complexity theory. Our construction combines ideas from a large body of prior work, ranging from a classical construction of [NN93] to the recent gradually increasing independence paradigm of [KMN11, CRSW13, GMRTV12], while also introducing some novel analytic machinery which might find other applications.
FOS: Computer and information sciences, Probability in computer science (algorithm analysis, random structures, phase transitions, etc.), halfspaces, randomness, Computation Theory and Mathematics, Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.), Computational Complexity (cs.CC), Pure Mathematics, Mathematical Sciences, Computation Theory & Mathematics, Computer Science - Computational Complexity, Information and Computing Sciences, Fourier transform, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), pseudorandomness, Random number generation in numerical analysis
FOS: Computer and information sciences, Probability in computer science (algorithm analysis, random structures, phase transitions, etc.), halfspaces, randomness, Computation Theory and Mathematics, Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.), Computational Complexity (cs.CC), Pure Mathematics, Mathematical Sciences, Computation Theory & Mathematics, Computer Science - Computational Complexity, Information and Computing Sciences, Fourier transform, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), pseudorandomness, Random number generation in numerical analysis
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 17 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
