DIMACS TR: 97-81
On Arithmetic Branching Programs
Authors: Amos Beimel and Anna Gál
ABSTRACT
We consider the model of arithmetic branching programs, which is a
generalization of modular branching programs. We show that, up to a
polynomial factor in size, arithmetic branching programs are
equivalent to complements of dependency programs, a model introduced
by Pudlak and Sgall in 1996. Using this equivalence we prove that
dependency programs are closed under conjunction, answering an open
problem of Pudlak and Sgall. Furthermore, we show that span programs,
an algebraic model of computation introduced by Karchmer and
Wigderson in 1993, are at least as strong as arithmetic programs;
every arithmetic program can be simulated by a span program of size
not more than twice the size of the arithmetic program. Using the
above results we give a new proof that the class NL/poly is contained
in the class parity-L/poly, first proved by Wigderson in 1994. Our
simulation of NL/poly is more efficient, and it holds for logspace
counting classes over every field.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-81.ps.gz
DIMACS Home Page