Extractors for polynomial sources over F₂

DOI10.4230/LIPICS.ITCS.2024.28MaRDI QIDQ6906408zbMATH OpenFDO

Authors Eshan Chattopadhyay, Jesse Goodman, Mohit Gurumukhani

Publication date 4 November 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2024.28

zbMATH Keywords

extractorslow-degree polynomialssumset extractorsvarieties

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A Pseudorandom Generator from any One-way Function
• A Small Maximal Sidon Set in ${\mathbb{Z}}_2^n$
• Affine dispersers from subspace polynomials
• Affine extractors for almost logarithmic entropy
• Affine extractors over large fields with exponential error
• Affine extractors over prime fields
• Deterministic extractors for affine sources over large fields
• Deterministic extractors for small-space sources
• Dispersers for Affine Sources with Sub-polynomial Entropy
• Extractors and lower bounds for locally samplable sources
• Extractors and rank extractors for polynomial sources
• Extractors for circuit sources
• Extractors for Images of Varieties
• Extractors for polynomial sources over fields of constant order and small characteristic
• Extractors for sum of two sources
• Extractors for varieties
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• Improved Extractors for Recognizable and Algebraic Sources
• Improved extractors for small-space sources
• Improved two-source extractors, and affine extractors for polylogarithmic entropy
• Low-degree polynomials extract from local sources
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• On a combinatorical problem of K. Zarankiewicz
• On the construction of affine extractors
• Pseudorandomness
• Simulating independence: new constructions of condensers, Ramsey graphs, dispersers, and extractors
• The Hilbert function, algebraic extractors, and recursive Fourier sampling
• Two source extractors for asymptotically optimal entropy, and (many) more
• Two structural results for low degree polynomials and applications
• Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds

Cited in

(3)

• Hilbert functions and low-degree randomness extractors
• Pseudo-random number generation with -encoders
• Low-degree polynomials are good extractors

This page was built for publication: Extractors for polynomial sources over \(\mathbb{F}_2\)

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