On hitting-set generators for polynomials that vanish rarely

DOI10.1007/s00037-022-00229-2OpenAlexW2982641353MaRDI QIDQ2099672

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Random low-degree polynomials are hard to approximate
The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
Generalized Hamming weights of affine Cartesian codes
Bemerkung zur vorstehenden Arbeit von Herrn Chevalley
Randomness is linear in space
Improved bounds for quantified derandomization of constant-depth circuits and polynomials
Hilbert functions and the finite degree Zariski closure in finite field combinatorial geometry
Extractors from Reed-Muller codes
On the structure of cubic and quartic polynomials
Polynomial Decompositions in Polynomial Time
Reed–Muller Codes for Random Erasures and Errors
Testers and their applications
On the size of Kakeya sets in finite fields
Pseudorandom Bits for Polynomials
Small-Bias Probability Spaces: Efficient Constructions and Applications
Asymptotically Optimal Hitting Sets Against Polynomials
Simple extractors for all min-entropies and a new pseudorandom generator
Extractor Codes
The distribution of polynomials over finite fields, with applications to the Gowers norms
Pseudorandom generators for low degree polynomials
Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
On Higher-Order Fourier Analysis over Non-Prime Fields
Quantified Derandomization: How to Find Water in the Ocean
Deconstructing 1-Local Expanders
On the Bias of Reed--Muller Codes over Odd Prime Fields
Sharp threshold results for computational complexity
Randomness efficient identity testing of multivariate polynomials
Bootstrapping results for threshold circuits “just beyond” known lower bounds
Quantified derandomization of linear threshold circuits
Ideals, Varieties, and Algorithms
On derandomizing algorithms that err extremely rarely
Weight Distribution and List-Decoding Size of Reed–Muller Codes
Algorithmic regularity for polynomials and applications
Restrictions on weight distribution of Reed-Muller codes
On the weight structure of Reed-Muller codes
Weight enumerator for second-order Reed-Muller codes
Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost

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