In a recent work, Gryaznov, Pudlák and Talebanfard (CCC '22) introduced a linear variant of read-once
branching programs, with motivations from circuit and proof complexity. Such a read-once linear branching program is
a branching program where each node is allowed to make $\mathbb{F}_2$-linear queries, and are read-once in the ... more >>>

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 >>>

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 >>>