Pseudorandom bits for polynomials

DOI10.1137/070712109MaRDI QIDQ3068640zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

explicitly computable generatorsgenerators that fool polynomialsGowers normpseudorandom generator

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20)

Recommendations

• Unconditional pseudorandom generators for low degree polynomials
• Pseudorandom generators for low degree polynomials
• Pseudorandom generators for \(\mathrm{CC}^0[p]\) and the Fourier spectrum of low-degree polynomials over finite fields
• The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
• More on bounded independence plus noise: pseudorandom generators for read-once polynomials

Cited in

(37)

• Optimal characteristic polynomials for digital multistep pseudorandom numbers
• 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
• Unconditional pseudorandom generators for low degree polynomials
• A dichotomy for local small-bias generators
• Cryptographic hardness of random local functions. Survey
• Small Sample Spaces Cannot Fool Low Degree Polynomials
• Pseudorandom generators for low degree polynomials
• Pseudorandom Bit Generators That Fool Modular Sums
• 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
• A polylogarithmic PRG for degree 2 threshold functions in the Gaussian setting
• Bounded independence plus noise fools products
• Luby-Veličković-Wigderson revisited: improved correlation bounds and pseudorandom generators for depth-two circuits
• Quantified Derandomization: How to Find Water in the Ocean
• scientific article; zbMATH DE number 7528580 (Why is no real title available?)
• Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
• More on bounded independence plus noise: pseudorandom generators for read-once polynomials
• The communication complexity of addition
• Counting solutions to polynomial systems via reductions
• Reed-Muller Codes
• Improved pseudorandom generators from pseudorandom multi-switching lemmas
• A simple deterministic reduction for the gap minimum distance of code problem
• Paradigms for Unconditional Pseudorandom Generators
• Partition and analytic rank are equivalent over large fields
• The Gowers U₃ norm of five classes of power permutations
• Pseudorandomness, symmetry, smoothing: I
• Optimal pseudorandom generators for low-degree polynomials over moderately large fields
• A non-trivial algorithm enumerating relevant features over finite fields
• The Gowers U₃ norm of one family of cubic power permutations
• On pseudorandom numbers from multivariate polynomial systems
• Fourier conjectures, correlation bounds, and majority
• Low-degree polynomials are good extractors
• On sums of INW pseudorandom generators

This page was built for publication: Pseudorandom bits for polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3068640)