ECCC-Report TR96-036https://eccc.weizmann.ac.il/report/1996/036Comments and Revisions published for TR96-036en-usWed, 26 Jun 1996 00:00:00 +0300
Revision 1
| A large lower bound for 1-branching programs Revision of: TR96-036 |
Petr Savicky,
Stanislav Zak
https://eccc.weizmann.ac.il/report/1996/036#revision1 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.
Wed, 26 Jun 1996 00:00:00 +0300https://eccc.weizmann.ac.il/report/1996/036#revision1
Paper TR96-036
| A large lower bound for 1-branching programs |
Petr Savicky,
Stanislav Zak
https://eccc.weizmann.ac.il/report/1996/036Branching 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.
Tue, 11 Jun 1996 14:19:37 +0300https://eccc.weizmann.ac.il/report/1996/036