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 >>>

Polynomial factorization is a fundamental problem in computational algebra. Over the past half century, a variety of algorithmic techniques have been developed to tackle different variants of this problem. In parallel, algebraic complexity theory classifies polynomials into complexity classes based on their perceived `hardness'. This raises a natural question: Do ... more >>>