2026-10-11T04:21:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25336 2026-03-19T12:03:41Z ddc:004 open_access

Debordering Closure Results in Determinantal and Pfaffian Ideals Dey, Anakin Guo, Zeyu Algebraic circuit complexity Isolation lemma Debordering One important question in algebraic complexity is understanding the complexity of polynomial ideals (Grochow, Bulletin of EATCS 131, 2020). Andrews and Forbes (STOC 2022) studied the determinantal ideals I^{det}_{n,m,r} generated by the r× r minors of n× m matrices. Over fields of characteristic zero or of sufficiently large characteristic, they showed that for any nonzero f ∈ I^{det}_{n,m,r}, the determinant of a t × t matrix of variables with t = Θ{r^{1/3}} is approximately computed by a constant-depth, polynomial-size f-oracle algebraic circuit, in the sense that the determinant lies in the border of such circuits. An analogous result was also obtained for Pfaffians in the same paper. In this work, we deborder the result of Andrews and Forbes by showing that when f has polynomial degree, the determinant is in fact exactly computed by a constant-depth, polynomial-size f-oracle algebraic circuit. We further establish an analogous result for Pfaffian ideals. Our results are established using the isolation lemma, combined with a careful analysis of straightening-law expansions of polynomials in determinantal and Pfaffian ideals. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anakin Dey and Zeyu Guo 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.49 urn:nbn:de:0030-drops-253363 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.49 eng https://creativecommons.org/licenses/by/4.0/legalcode