Talk
Dimension of algebraic branching program width varieties
- Pierpaola Santarsiero (University of Warsaw)
Abstract
An Algebraic Branching Program (ABP) for a degree d homogeneous polynomial F is a layered directed acyclic graph with d+1 layers, where edges are labeled by linear forms and F is obtained as the sum over all source-to-sink paths of the products of the edge labels along the path. The width of an ABP is the maximal number of nodes over any intermediate layer, and the width of F is the minimal width among all ABPs representing F.
Motivated by problems in algebraic complexity theory, we are currently studying dimensions of varieties of forms with bounded ABP width. This is a work in progress with Chia-Yu Chang.
