Loading jsMath...
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