Revision #1 Authors: Petr Savicky, Stanislav Zak

Accepted on: 26th June 1996 00:00

Downloads: 2031

Keywords:

Branching programs (b.p.'s) or decision diagrams are a general

graph-based model of sequential computation. B.p.'s of polynomial

size are a nonuniform counterpart of LOG. Lower bounds for

different kinds of restricted b.p.'s are intensively investigated.

An important restriction are so called 1-b.p.'s, where each

computation reads each input bit at most once. There is a series

of lower bounds for 1-b.p.'s. The largest known lower bound is

due to J. Simon and M. Szegedy (improving a result of L. Babai,

P. Hajnal, E. Szemeredi and G. Turan) and it is $2^{n/2000}$

for an explicit function of $n$ variables. In the present paper,

a lower bound of $2^{n-o(n)}$ is given for another explicit function.

A generalization of the construction is also presented that

may in principle lead to lower bound that almost matches a

general upper bound.

TR96-036 Authors: Petr Savicky, Stanislav Zak

Publication: 11th June 1996 14:19

Downloads: 1268

Keywords:

Branching programs (b.p.'s) or decision diagrams are a general

graph-based model of sequential computation. B.p.'s of polynomial

size are a nonuniform counterpart of LOG. Lower bounds for

different kinds of restricted b.p.'s are intensively investigated.

An important restriction are so called 1-b.p.'s, where each

computation reads each input bit at most once. There is a series

of lower bounds for 1-b.p.'s. The largest known lower bound is

due to J. Simon and M. Szegedy (improving a result of L. Babai,

P. Hajnal, E. Szemeredi and G. Turan) and it is $2^{n/2000}$

for an explicit function of $n$ variables. In the present paper,

a lower bound of $2^{n-o(n)}$ is given for another explicit function.