Assume indistinguishability obfuscation (iO) and one-way functions, both secure against nonuniform polynomial-size adversaries. We show that no randomized polynomial-size pruning procedure isolates a witness with probability at least a/log L, for any constant a > 0, where L is the length of the circuit description. Dell, Kabanets, van Melkebeek, and ... more >>>

Local LCL properties [Levi, Mosheiff, and Shagrithaya (LMS), FOCS 2025] give a language to express a broad range of linear properties of codes. Subspace design [Guruswami and Xing, 2013] is an elegant property about the linear structure of codes, and it governs important code behavior. In this note, we show ... more >>>

We prove that every finite two-player game $G$ with entangled value $\omega^*(G)=1-\epsilon$ satisfies
\[
\omega^*(G^{\otimes n})
\le\exp(-\Omega(\frac{\epsilon^3}{\epsilon+ \ell }n))
\]
for every $n\ge1$, where $\ell:=\log(|A| |B|)$, and $A$ and $B$ are the answer alphabets. Compared with Chapter 6 of the OpenAI report [Ope26], this improves the gap exponent from thirteen ... more >>>