Pseudorandom Bits for Polynomials
From MaRDI portal
Publication:3068640
DOI10.1137/070712109zbMath1211.68215OpenAlexW2034946612MaRDI 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
Number-theoretic algorithms; complexity (11Y16) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (22)
Succinct non-interactive arguments via linear interactive proofs ⋮ A dichotomy for local small-bias generators ⋮ Quantified Derandomization: How to Find Water in the Ocean ⋮ 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 ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Partition and analytic rank are equivalent over large fields ⋮ Unnamed Item ⋮ The inverse conjecture for the Gowers norm over finite fields in low characteristic ⋮ Counting Solutions to Polynomial Systems via Reductions ⋮ Small Sample Spaces Cannot Fool Low Degree Polynomials ⋮ Bounded Independence Plus Noise Fools Products ⋮ The communication complexity of addition ⋮ Unnamed Item ⋮ A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem ⋮ Improved bounds for quantified derandomization of constant-depth circuits and polynomials ⋮ Unnamed Item ⋮ Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition ⋮ On hitting-set generators for polynomials that vanish rarely ⋮ Reed-Muller Codes
This page was built for publication: Pseudorandom Bits for Polynomials
