Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Lower Bounds for Syntactically Multilinear Algebraic Branching Programs

Edit abstract data

Speaker: Maurice Jansen
Slot: Wed, 16:50-17:10, Room 20 (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 Valid HTML 4.01! Valid CSS!