All known proofs of the PCP theorem rely on multiple "composition" steps, where PCPs over large alphabets are turned into PCPs over much smaller alphabets at a (relatively) small price in the soundness error of the PCP. Algebraic proofs, starting with the work of Arora, Lund, Motwani, Sudan, and Szegedy ... more >>>

We give versions of Shannon's coding theorem where the decoder runs in constant time:

- Let $D=(D_1,D_2,\ldots,D_n)$ be a product distribution where the $D_i$ have constant support and have dyadic probability masses (i.e., of the form $a/2^b$ where $a,b$ are integers). Then $D$ can be sampled in constant time in ... more >>>

Consider a function that is mildly hard for size-$s$ circuits. For sufficiently large $s$, Impagliazzo's hardcore lemma guarantees a constant-density subset of inputs on which the same function is extremely hard for circuits of size $s'<\!\!<s$. Blanc, Hayderi, Koch, and Tan [FOCS 2024] recently showed that the degradation from $s$ ... more >>>