Abstract

A central question in algebraic complexity theory is understanding the behaviour of polynomial computation models under basic algebraic operations. While closure under addition and multiplication holds for most of the standard models like algebraic circuits, closure under factorisation remains subtle. In this talk, we will discuss a new result which proves that the well-studied model called read-once oblivious algebraic branching programs (ROABPs) is not closed under factoring. This result offers a contrasting perspective to recent breakthrough work that gave a unified framework for proving closure under factorisation in other regimes. We will also discuss similar non-closure properties of ROAB Ps under other natural operations such as powering and symmetric composition.

This is based on joint work with Andrews, Armand, Hansen, Limaye, Srinivasan, and Tavenas.