Alladi Ramakrishnan Hall

Nonnegative rank measures and monotone algebraic branching programs

Sebastien Tavenas

Université Savoie Mont Blanc, France

Inspired by Nisan’s characterization of noncommutative complexity (Nisan 1991), we will focus on the links between the nonnegative rank and the complexity of monotone computations. In particular, we answer negatively an open question of Nisan asking whether nonnegative rank characterizes monotone noncommutative complexity for algebraic branching programs. On the way, we will also consider some weaker semantic versions of the nonnegative rank and of the monotone computations.

We will finish by proving some tight lower bounds for the computation of elementary symmetric polynomials by algebraic branching programs in the monotone setting or, equivalently, in the homogeneous syntactically multilinear setting.

This work will appear in FSTTCS 2019, it was done with H.Fournier, G.Malod and M.Szusterman.