![[Search]](/static/images/search.gif){kind=small}
![[A-Z Index]](/static/images/az.gif){kind=small}
![[Contact]](/static/images/contact.gif){kind=small}
![[University of Cambridge]](/static/images/identifier2.gif){kind=small}
![[Talks.cam]](/static/images/talkslogosmall.gif)
Prateek Dwivedi
Friday 27 March 2026, 14:00-15:00
Non-Closure Properties of Read-Once Oblivious Algebraic Branching Programs
- đ¤ Speaker: Prateek Dwivedi
- đ Date & Time: Friday 27 March 2026, 14:00 - 15:00
- đ Venue: SS03, Computer Laboratory
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.
Series This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.
Included in Lists
- All Talks (aka the CURE list)
- bld31
- Cambridge talks
- Computing and Mathematics
- Department of Computer Science and Technology talks and seminars
- Interested Talks
- Logic and Semantics Seminar (Computer Laboratory)
- Martin's interesting talks
- School of Technology
- SS03, Computer Laboratory
- tcw57âs list
- Trust & Technology Initiative - interesting events
- yk373's list
- yk449
Note: Ex-directory lists are not shown.