Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > JULES ARMAND:
All reports by Author Jules Armand:

TR25-135 | 13th September 2025
Jules Armand, Prateek Dwivedi, Nutan Limaye, Magnus Rahbek Dalgaard Hansen, Srikanth Srinivasan, Sébastien Tavenas

On Closure Properties of Read-Once Oblivious Algebraic Branching Programs

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_1,\ldots, x_n))_n$ that have poly(n)-sized roABPs such that some irreducible factor of $f_n$ does not have roABPs ... more >>>




ISSN 1433-8092 | Imprint