research
∙
09/20/2023
Extractors for Polynomial Sources over 𝔽_2
We explicitly construct the first nontrivial extractors for degree d ≥ 2...
share
research
∙
09/08/2023
Recursive Error Reduction for Regular Branching Programs
In a recent work, Chen, Hoza, Lyu, Tal and Wu (FOCS 2023) showed an impr...
research
∙
05/27/2022
Low-Degree Polynomials Extract from Local Sources
We continue a line of work on extracting random bits from weak sources t...
research
∙
10/25/2021
Extractors for Sum of Two Sources
We consider the problem of extracting randomness from sumset sources, a ...
research
∙
08/04/2020
Fractional Pseudorandom Generators from Any Fourier Level
We prove new results on the polarizing random walk framework introduced ...
research
∙
07/15/2020
Explicit Designs and Extractors
We give significantly improved explicit constructions of three related p...
research
∙
02/17/2020
Optimal Error Pseudodistributions for Read-Once Branching Programs
In 1992, Nisan (Combinatorica'92) constructed a pseudorandom generator f...
research
∙
04/14/2018