2026-09-20T12:50:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25296 2026-09-05T19:12:14Z ddc:004 open_access

On Closure Properties of Read-Once Oblivious Algebraic Branching Programs Andrews, Robert Armand, Jules Dwivedi, Prateek Hansen, Magnus Rahbek Dalgaard Limaye, Nutan Srinivasan, Srikanth Tavenas, Sébastien Factoring Closure Properties Sparsity Bounds Symmetric Polynomials roABP Expander Graphs We investigate the closure properties of read-once oblivious Algebraic Branching Programs (roABPs) under various natural algebraic operations and prove the following. - Non-closure under factoring: There is a sequence of explicit polynomials (f_n(x₁,…, x_n))_n that have poly(n)-sized roABPs such that some irreducible factor of f_n requires roABPs of superpolynomial size in any order. - Non-closure under powering: There is a sequence of polynomials (f_n(x₁,…, x_n))_n with poly(n)-sized roABPs such that any super-constant power of f_n does not have roABPs of polynomial size in any order (and f_nⁿ requires exponential size in any order). - Non-closure under symmetric operations: There are symmetric polynomials (f_n(e₁,…, e_n))_n that have roABPs of polynomial size such that f_n(x₁,…, x_n) do not have roABPs of subexponential size. (Here, e₁,…, e_n denote the elementary symmetric polynomials in n variables.) These results should be viewed in light of known results on models such as algebraic circuits, (general) algebraic branching programs, formulas and constant-depth circuits, all of which are known to be closed under these operations. To prove non-closure under factoring, we construct hard polynomials based on expander graphs using gadgets that lift their hardness from sparse polynomials to roABPs. For symmetric compositions, we show that the circulant polynomial requires roABPs of exponential size in every variable order. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Robert Andrews and Jules Armand and Prateek Dwivedi and Magnus Rahbek Dalgaard Hansen and Nutan Limaye and Srikanth Srinivasan and Sébastien Tavenas 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.9 urn:nbn:de:0030-drops-252964 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.9 eng https://creativecommons.org/licenses/by/4.0/legalcode