Pseudorandomness via the Discrete Fourier Transform
| Autor: | Raghu Meka, Parikshit Gopalan, Daniel M. Kane |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
FOS: Computer and information sciences
General Computer Science medicine.medical_treatment General Mathematics Pseudorandomness randomness Pseudorandom generator 0102 computer and information sciences Computer Science::Computational Complexity Computational Complexity (cs.CC) 01 natural sciences Discrete Fourier transform Computation Theory & Mathematics 010104 statistics & probability symbols.namesake Discrete Fourier transform (general) medicine Applied mathematics 0101 mathematics Randomness Computer Science::Cryptography and Security Mathematics Discrete mathematics Pseudorandom number generator Linear function (calculus) Computation Theory And Mathematics halfspaces TheoryofComputation_GENERAL Pseudorandom generator theorem Pure Mathematics Computer Science - Computational Complexity Fourier transform 010201 computation theory & mathematics symbols Pseudorandom generators for polynomials pseudorandomness Algorithm Generator (mathematics) |
| Zdroj: | Gopalan, Parikshit; Kane, Daniel M; & Meka, Raghu. (2018). PSEUDORANDOMNESS VIA THE DISCRETE FOURIER TRANSFORM. SIAM JOURNAL ON COMPUTING, 47(6), 2451-2487. doi: 10.1137/16M1062132. UC San Diego: Retrieved from: http://www.escholarship.org/uc/item/6tj2z2c9 SIAM JOURNAL ON COMPUTING, vol 47, iss 6 FOCS SIAM Journal on Computing, vol 47, iss 6 |
| ISSN: | 1095-7111 0097-5397 |
| DOI: | 10.1137/16m1062132 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|