OpenAI's Sep 2026 preprint introduced the first cubic lower bound on the border DC of the permanent. Their preprint generalizes the method I introduced in my June 2026 preprint (https://arxiv.org/abs/2606.15970; see also TR26-275). However, their proof only applies over $\mathbb{C}$.

In this note, I prove that the cubic lower bound ... more >>>

The plural in the title hints that there are several complexities involved here.
The most traditional one is the computational complexity of the verifier; but, in the context of Interactive Proofs of Proximity (IPPs), the query complexity of the verifier and the communication complexity of the system should ... more >>>

In a $k$-XOR game $\Psi$ over $\mathbb{F}_p$, a verifier samples challenges $(x_1,\ldots,x_k)\sim\mu$ where $\mu$ is a distribution over $\Sigma_1\times\ldots\times \Sigma_k$, sends $x_i$ to player $i$ and receives an answer $f_i(x_i)\in\mathbb{F}_p$, and accepts if and only if $f_1(x_1)+\ldots+f_k(x_k)=t(x_1,\ldots,x_k)$, where $t\colon \Sigma_1\times\ldots\times \Sigma_k\to\mathbb{F}_p$ is a fixed map. We show that if $\Psi$ ... more >>>