On hitting-set generators for polynomials that vanish rarely

DOI10.1007/S00037-022-00229-2MaRDI QIDQ2099672zbMATH OpenOpenAlexFDO

Authors Dean Doron, Amnon Ta-Shma, Roei Tell

Publication date 24 November 2022

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-022-00229-2

bounded-degree closure hitting-set generators polynomials pseudorandom generators quantified derandomization

Polynomials over finite fields (11T06) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

On hitting-set generators for polynomials that vanish rarely
Pseudorandom generators for low degree polynomials
Asymptotically Optimal Hitting Sets Against Polynomials
Pseudorandom bits for polynomials
Randomness efficient testing of sparse black box identities of unbounded degree over the reals

Cites work

Algorithmic regularity for polynomials and applications
Asymptotically Optimal Hitting Sets Against Polynomials
Bemerkung zur vorstehenden Arbeit von Herrn Chevalley
Bootstrapping results for threshold circuits ``just beyond known lower bounds
Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
Deconstructing 1-Local Expanders
Extractor Codes
Extractors from Reed-Muller codes
Generalized Hamming weights of affine Cartesian codes
Hilbert functions and the finite degree Zariski closure in finite field combinatorial geometry
scientific article; zbMATH DE number 3577144 (Why is no real title available?)
scientific article; zbMATH DE number 1775429 (Why is no real title available?)
scientific article; zbMATH DE number 7758310 (Why is no real title available?)
Ideals, Varieties, and Algorithms
Improved bounds for quantified derandomization of constant-depth circuits and polynomials
Luby-Veličković-Wigderson revisited: improved correlation bounds and pseudorandom generators for depth-two circuits
On derandomizing algorithms that err extremely rarely
On higher-order Fourier analysis over non-prime fields
On the bias of Reed-Muller codes over odd prime fields
On the size of Kakeya sets in finite fields
On the structure of cubic and quartic polynomials
On the weight structure of Reed-Muller codes
Polynomial decompositions in polynomial time
Pseudorandom bits for polynomials
Pseudorandom generators for low degree polynomials
Quantified derandomization of linear threshold circuits
Quantified Derandomization: How to Find Water in the Ocean
Random low-degree polynomials are hard to approximate
Randomness efficient identity testing of multivariate polynomials
Randomness is linear in space
Reed–Muller Codes for Random Erasures and Errors
Restrictions on weight distribution of Reed-Muller codes
Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
Satisfiability and derandomization for small polynomial threshold circuits
Sharp threshold results for computational complexity
Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost
Simple extractors for all min-entropies and a new pseudorandom generator
Small-Bias Probability Spaces: Efficient Constructions and Applications
Testers and their applications
The distribution of polynomials over finite fields, with applications to the Gowers norms
The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
Unconditional pseudorandom generators for low degree polynomials
Weight Distribution and List-Decoding Size of Reed–Muller Codes
Weight enumerator for second-order Reed-Muller codes

Cited in

(4)

Reconstructive dispersers and hitting set generators
Asymptotically Optimal Hitting Sets Against Polynomials
On hitting-set generators for polynomials that vanish rarely
Hilbert functions and low-degree randomness extractors

This page was built for publication: On hitting-set generators for polynomials that vanish rarely

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