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

Gowers normpseudorandom generatorexplicitly computable generatorsgenerators that fool polynomials

Mathematics Subject Classification ID

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

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

(28)

• Luby-Veličković-Wigderson revisited: improved correlation bounds and pseudorandom generators for depth-two circuits
• On hitting-set generators for polynomials that vanish rarely
• Pseudorandom generators for \(\mathrm{CC}^0[p]\) and the Fourier spectrum of low-degree polynomials over finite fields
• Pseudorandom generators for combinatorial checkerboards
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• Improved bounds for quantified derandomization of constant-depth circuits and polynomials
• Paradigms for Unconditional Pseudorandom Generators
• On pseudorandom numbers from multivariate polynomial systems
• The inverse conjecture for the Gowers norm over finite fields in low characteristic
• Pseudorandom Bit Generators That Fool Modular Sums
• Succinct non-interactive arguments via linear interactive proofs
• A simple deterministic reduction for the gap minimum distance of code problem
• A dichotomy for local small-bias generators
• A polylogarithmic PRG for degree 2 threshold functions in the Gaussian setting
• scientific article; zbMATH DE number 7528580 (Why is no real title available?)
• scientific article; zbMATH DE number 7650112 (Why is no real title available?)
• Cryptographic hardness of random local functions. Survey
• Quantified Derandomization: How to Find Water in the Ocean
• Reed-Muller Codes
• Pseudorandom generators for low degree polynomials
• Optimal characteristic polynomials for digital multistep pseudorandom numbers
• Bounded independence plus noise fools products
• More on bounded independence plus noise: pseudorandom generators for read-once polynomials
• Partition and analytic rank are equivalent over large fields
• Counting solutions to polynomial systems via reductions
• Unconditional pseudorandom generators for low degree polynomials
• The communication complexity of addition
• Small Sample Spaces Cannot Fool Low Degree Polynomials

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)