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

We study whether lower bounds against constant-depth algebraic circuits computing the Permanent over finite fields (Limaye–Srinivasan–Tavenas [J. ACM, 2025] and Forbes [CCC’24]) are hard to prove in certain proof systems. We focus on a DNF formula that expresses that such lower bounds are hard for constant-depth algebraic proofs. Using an ... more >>>

Proving lower bounds on the size of noncommutative arithmetic circuits is an important problem in arithmetic circuit complexity. For explicit $n$ variate polynomials of degree $\Theta(n)$, the best known general bound is $\Omega(n \log n)$. Recent work of Chatterjee and Hrubeš has provided stronger ($\Omega(n^2)$) bounds for the restricted class ... more >>>