Non-Closure properties in algebraic complexity by Dr. Prateek Dwivedi

Venue: Bharti501

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 offers a contrasting perspective in light of the recent breakthrough work that proved a unified framework for analysing closure under factorisation. We will also discuss similar non-closure properties of roABP under other natural operations such as powering and symmetric composition.

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

[arxiv]