DIMACS TR: 97-81

On Arithmetic Branching Programs

Authors: Amos Beimel and Anna Gál


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