An algebraic branching program (ABP) over a field is an edge-labeled acyclic digraph with a distinguished
source 
and target 
.
Edge labels are usually variables or affine linear forms. The polynomial computed
by the program is
 |
where the product is taken in path order. The same definition can be made over a semiring; for noncommuting labels, the order of the factors is essential.
An algebraic branching program is layered if every edge goes from one layer to the next. Its width is the maximum number of vertices in a layer. If the transition matrices
between successive layers are 
, 
, ..., 
, then the computed polynomial is an entry, or more generally
a bilinear form,
 |
of their product. Thus bounded-width algebraic branching programs are closely related to iterated matrix multiplication (Bringmann et al. 2018).
The size of an algebraic branching program is commonly measured by its number of vertices or edges, depending on convention. This is a shared directed-graph model and therefore differs from the size of an algebraic formula, in which every repeated occurrence of a subexpression is counted separately. Algebraic branching programs are used in both commutative and noncommutative algebraic complexity (Nisan 1991).
