Pseudorandom generators for low degree polynomials

DOI10.1145/1060590.1060594MaRDI QIDQ3581382zbMATH OpenOpenAlexFDO

Authors Andrej Bogdanov

Publication date 16 August 2010

Published in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1060590.1060594

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Recommendations

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

Cited in

(28)

• On hitting-set generators for polynomials that vanish rarely
• Improved bounds for quantified derandomization of constant-depth circuits and polynomials
• Exact learning from an honest teacher that answers membership queries
• Unconditional pseudorandom generators for low degree polynomials
• Pseudorandom bits for polynomials
• Small Sample Spaces Cannot Fool 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
• Pseudorandomness via the discrete Fourier transform
• A polylogarithmic PRG for degree 2 threshold functions in the Gaussian setting
• 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?)
• Hitting sets give two-sided derandomization of small space
• scientific article; zbMATH DE number 7250141 (Why is no real title available?)
• scientific article; zbMATH DE number 7250142 (Why is no real title available?)
• More on bounded independence plus noise: pseudorandom generators for read-once polynomials
• Pseudorandom generators from polarizing random walks
• Improved pseudorandom generators from pseudorandom multi-switching lemmas
• On hitting-set generators for polynomials that vanish rarely
• scientific article; zbMATH DE number 7758310 (Why is no real title available?)
• The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
• Variety evasive subspace families
• Derandomizing multivariate polynomial factoring for low degree factors
• Optimal pseudorandom generators for low-degree polynomials over moderately large fields
• On pseudorandom numbers from multivariate polynomial systems
• Deterministically testing sparse polynomial identities of unbounded degree

This page was built for publication: Pseudorandom generators for low degree polynomials

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