Logical Approaches to Computational Barriers

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 considered.

websites: Arnold Beckmann | 2008-06-03 |