Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > POLYNOMIAL-MAP:
Reports tagged with polynomial-map:
TR23-140 | 20th September 2023
Eshan Chattopadhyay, Jesse Goodman, Mohit Gurumukhani

Extractors for Polynomial Sources over $\mathbb{F}_2$

Revisions: 1

We explicitly construct the first nontrivial extractors for degree $d \ge 2$ polynomial sources over $\mathbb{F}_2^n$. Our extractor requires min-entropy $k\geq n - \frac{\sqrt{\log n}}{(d\log \log n)^{d/2}}$. Previously, no constructions were known, even for min-entropy $k\geq n-1$. A key ingredient in our construction is an input reduction lemma, which allows ... more >>>




ISSN 1433-8092 | Imprint