Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
Lower Bounds for Syntactically Multilinear Algebraic Branching Programs

Speaker: Maurice Jansen
Slot: Array, 16:50-17:10, col. 1


It is demonstrated that any weakly-skew circuit can be converted into a skew
circuit with constant factor overhead, while preserving either syntactic or
semantic multilinearity. This leads to considering multilinear algebraic
branching programs (ABPs), which are defined by a natural read-once property. A
2^{n/4} lower bound for the size of ordered multilinear ABPs computing an
explicitly constructed multilinear polynomial in 2n variables is proven.
Without the ordering restriction a lower bound of level n^{3/2}/log n is
observed. For this a generalization of a hypercube covering problem by Galvin is

websites: Arnold Beckmann 2008-06-03