Pseudorandom Bits for Polynomials
From MaRDI portal
Publication:3068640
DOI10.1137/070712109zbMath1211.68215MaRDI QIDQ3068640
Andrej Bogdanov, Emanuele Viola
Publication date: 17 January 2011
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/070712109
pseudorandom generator; Gowers norm; explicitly computable generators; generators that fool polynomials
11Y16: Number-theoretic algorithms; complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
68W20: Randomized algorithms
68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Related Items
Bounded Independence Plus Noise Fools Products, Unnamed Item, Unnamed Item, Unnamed Item, Quantified Derandomization: How to Find Water in the Ocean, Counting Solutions to Polynomial Systems via Reductions, Unnamed Item, A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem, Reed-Muller Codes, Paradigms for Unconditional Pseudorandom Generators, Partition and analytic rank are equivalent over large fields, A dichotomy for local small-bias generators, Cryptographic hardness of random local functions. Survey, Pseudorandom generators for \(\mathrm{CC}^0[p\) and the Fourier spectrum of low-degree polynomials over finite fields], Pseudorandom generators for combinatorial checkerboards, The inverse conjecture for the Gowers norm over finite fields in low characteristic, The communication complexity of addition, On hitting-set generators for polynomials that vanish rarely, Succinct non-interactive arguments via linear interactive proofs, Improved bounds for quantified derandomization of constant-depth circuits and polynomials, Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition, Small Sample Spaces Cannot Fool Low Degree Polynomials
