In a recent work, Chen, Hoza, Lyu, Tal and Wu (FOCS 2023) showed an improved error reduction framework for the derandomization of regular read-once branching programs (ROBPs). Their result is based on a clever modification to the inverse Laplacian perspective of space-bounded derandomization, which was originally introduced by Ahmadinejad, Kelner, ... more >>>

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 consider the problem of extracting randomness from \textit{sumset sources}, a general class of weak sources introduced by Chattopadhyay and Li (STOC, 2016). An (n,k,C)-sumset source \mathbf{X} is a distribution on \{0,1\}^n of the form \mathbf{X}_1 + \mathbf{X}_2 + \ldots + \mathbf{X}_C, where \mathbf{X}_i's are independent sources on n bits ... more >>>

We give an explicit construction of an affine extractor (over \mathbb{F}_2) that works for affine sources on n bits with min-entropy k \ge~ \log n \cdot (\log \log n)^{1 + o(1)}. This improves prior work of Li (FOCS'16) that requires min-entropy at least \mathrm{poly}(\log n).

Our construction is ... more >>>

In a seminal work, Nisan (Combinatorica'92) constructed a pseudorandom generator for length n and width w read-once branching programs with seed length O(\log n\cdot \log(nw)+\log n\cdot\log(1/\varepsilon)) and error \varepsilon. It remains a central question to reduce the seed length to O(\log (nw/\varepsilon)), which would prove that \mathbf{BPL}=\mathbf{L}. However, there has ... more >>>

We present the first explicit construction of a non-malleable code that can handle tampering functions that are bounded-degree polynomials.

Prior to our work, this was only known for degree-1 polynomials (affine tampering functions), due to Chattopadhyay and Li (STOC 2017). As a direct corollary, we obtain an explicit non-malleable ... more >>>