2 papers
cs.CC2025
On Closure Properties of Read-Once Oblivious Algebraic Branching Programs
Jules Armand, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen +3
We investigate the closure properties of read-once oblivious Algebraic Branching Programs (roABPs) under various natural algebraic operations and prove the following. - Non-closure…
cs.CC2025
The Algebraic Cost of a Boolean Sum
Ian Orzel, Srikanth Srinivasan, Sébastien Tavenas +1
It is a well-known fact that the permanent polynomial is complete for the complexity class VNP, and it is largely suspected that the determinant does not share this property, despi…