A natural model of a source of randomness consists of a long stream of symbols $X = X_1\circ\ldots\circ X_t$, with some guarantee on the entropy of $X_i$ conditioned on the outcome of the prefix $x_1,\dots,x_{i-1}$. We study unpredictable sources, a generalization of the almost Chor--Goldreich (CG) sources considered in [DMOZ23]. ... more >>>

In this work, we show that the class of multivariate degree-$d$ polynomials mapping $\{0,1\}^{n}$ to any Abelian group $G$ is locally correctable with $\widetilde{O}_{d}((\log n)^{d})$ queries for up to a fraction of errors approaching half the minimum distance of the underlying code. In particular, this result holds even for polynomials ... more >>>

This note revisits the study of search problems that are solvable in probabilistic polynomial time. Previously, Goldreich (2011) introduced a class called ``$\mathcal{BPP}$-search'', and studied search-to-decision reductions for problems in this class.

In Goldreich's original formulation, the definition of what counts as ``successfully solving'' a $\mathcal{BPP}$-search problem is implicit, and ... more >>>