Randomness extractors provide a generic way of converting sources of randomness that are
merely unpredictable into almost uniformly random bits. While in general, deterministic randomness
extraction is impossible, it is possible if the source has some structural constraints.
While much of the literature on deterministic extraction has focused on sources ... more >>>

We prove that for every $\alpha \in [1,1.5]$,
$$
\text{BPSPACE}[S]\subseteq \text{TISP}[2^{S^{\alpha}},S^{3-\alpha}]
$$
where $\text{BPSPACE}[S]$ corresponds to randomized space $O(S)$ computation, and $\text{TISP}[T,S]$ to time $poly(T)$, space $O(S)$ computation. Our result smoothly interpolates between the results of (Nisan STOC 1992) and (Saks and Zhou FOCS 1995), which prove $\text{BPSPACE}[S]$ is contained ... more >>>

We give an explicit construction of non-malleable codes with rate $1-o(1)$ for the tampering class of poly-size circuits. This rate is optimal, and improves upon the previous explicit construction of Ball, Dachman-Soled and Loss (CRYPTO 2022) which achieves a rate smaller than $\frac{1}{n}$. Our codes are based on the same ... more >>>