Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > POLYNOMIAL SOURCES:
Reports tagged with polynomial sources:
TR24-093 | 16th May 2024
Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff, Joao Ribeiro

Low-Degree Polynomials Are Good Extractors

We prove that random low-degree polynomials (over $\mathbb{F}_2$) are unbiased, in an extremely general sense. That is, we show that random low-degree polynomials are good randomness extractors for a wide class of distributions. Prior to our work, such results were only known for the small families of (1) uniform sources, ... more >>>




ISSN 1433-8092 | Imprint