Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR96-036 | 26th June 1996 00:00

A large lower bound for 1-branching programs Revision of: TR96-036

RSS-Feed




Revision #1
Authors: Petr Savicky, Stanislav Zak
Accepted on: 26th June 1996 00:00
Downloads: 1536
Keywords: 


Abstract:

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.


Paper:

TR96-036 | 28th May 1996 00:00

A large lower bound for 1-branching programs





TR96-036
Authors: Petr Savicky, Stanislav Zak
Publication: 11th June 1996 14:19
Downloads: 1091
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint