Pseudorandom bits for polynomials

DOI10.1137/070712109zbMATH Open1211.68215OpenAlexW2034946612MaRDI QIDQ3068640FDOQ3068640

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

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

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)

Cited In (28)

• 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
• Pseudorandom Bit Generators That Fool Modular Sums
• The inverse conjecture for the Gowers norm over finite fields in low characteristic
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Cryptographic hardness of random local functions. Survey
• Reed-Muller Codes
• Quantified Derandomization: How to Find Water in the Ocean
• Pseudorandom generators for low degree polynomials
• Bounded independence plus noise fools products
• Optimal characteristic polynomials for digital multistep pseudorandom numbers
• 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
• Luby-Veličković-Wigderson revisited: improved correlation bounds and pseudorandom generators for depth-two circuits

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)