Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-287 | 29th October 2026 20:59

Extending OpenAI's cubic lower bound for the permanent to odd characteristic, Pfaffian representations, and polynomial entries

RSS-Feed

Abstract:

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 holds over every algebraically closed field of odd characteristic $p$. Therefore, the cubic bound no longer depends on characteristic zero. I further prove the bound for Pfaffians. Recall that lower bounds for Pfaffians imply the same bounds for determinants. Finally, I prove the bound for matrices whose entries are polynomials of degree at most a. All three results come from the same lower bound for smooth hypersurfaces. Its proof involves counting intersection points together with their multiplicities, and applies to every characteristic.

\textbf{This article was written by the human author.}



ISSN 1433-8092 | Imprint