{"id":"openai-math/A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent","pdf":"https://github.com/openai/math/blob/main/preprints/A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent-September-24-2026/A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent-September-24-2026.pdf","url":"https://github.com/openai/math/tree/main/preprints/A-cubic-lower-bound-for-border-determinantal-complexity-of-the-permanent-September-24-2026","tags":["computational-complexity","determinantal-complexity","algebraic-complexity","permanent"],"score":0,"title":"A cubic lower bound for border determinantal complexity of the permanent","domain":"Theoretical computer science","family":"108","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"We prove that the complex border determinantal complexity of the $`m\\times m`$ permanent is $`\\Omega(m^3)`$, allowing arbitrary affine-linear determinant representations and coefficientwise limits. It also gives cubic lower bounds for exact determinantal complexity and for the numbers of vertices and edges in affine-linear algebraic branching programs, including coefficientwise limits with a fixed vertex or edge budget.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":1,"published":"2026-09-24","reactions":{},"discussion":[{"url":"https://scottaaronson.blog/?p=10169#:~:text=improving%20the%20previous%20best%20bound%20which%20was%20quadratic.","date":"2026-10-07","kind":"web","site":"Shtetl-Optimized","text":"improving the previous best bound which was quadratic. A randomized polytime algorithm to approximately count the number of perfect matchings in a general graph, as well as a randomized nearly linear-time algorithm for finding a maximum matching in such a graph A deterministic polynomial-time…","added":"2026-10-24","title":"The Mathocalypse"}],"formalized":false,"family_title":"A cubic permanent–determinant lower bound"}