Almost the same types of restricted branching programs (or binary decision diagrams BDDs) are considered in complexity theory and in applications like hardware verification. These models are read-once branching programs (free BDDs) and certain types of oblivious branching programs (ordered and indexed BDDs with k layers). The complexity of the ... more >>>

A syntactic read-k times branching program has the restriction that no variable occurs more than k times on any path (whether or not consistent). We exhibit an explicit Boolean function f which cannot be computed by nondeterministic syntactic read-k times branching programs of size less than exp(\sqrt{n}}k^{-2k}), although its complement ... more >>>

In unrestricted branching programs all variables may be tested arbitrarily often on each path. But exponential lower bounds are only known, if on each path the number of tests of each variable is bounded (Borodin, Razborov and Smolensky (1993)). We examine branching programs in which for each path the number ... more >>>

We prove an unexpected upper bound on a communication game proposed by Jeff Edmonds and Russell Impagliazzo as an approach for proving lower bounds for time-space tradeoffs for branching programs. Our result is based on a generalization of a construction of Erdos, Frankl and Rodl of a large 3-hypergraph with ... more >>>

This paper studies the learnability of branching programs and small depth circuits with modular and threshold gates in both the exact and PAC learning models with and without membership queries. Some of the results extend earlier works in [GG95,ERR95,BTW95]. The main results are as follows. For branching programs we show ... more >>>

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 ... more >>>

We investigate the computational complexity of the isomorphism problem for one-time-only branching programs (BP1-Iso): on input of two one-time-only branching programs B and B', decide whether there exists a permutation of the variables of B' such that it becomes equivalent to B. Our main result is a two-round interactive proof ... more >>>

Branching programs (b.p.'s) or decision diagrams are a general graph-based model of sequential computation. The 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 $k$-b.p.'s, where each computation reads each input bit ... more >>>

In the manuscript F. Ablayev and M. Karpinski, On the power of randomized branching programs (generalization of ICALP'96 paper results for the case of pure boolean function, available at http://www.ksu.ru/~ablayev) we exhibited a simple boolean functions $f_n$ in $n$ variables such that: 1) $f_{n}$ can be computed by polynomial size ... more >>>

Randomized branching programs are a probabilistic model of computation defined in analogy to the well-known probabilistic Turing machines. In this paper, we present complexity theoretic results for randomized read-once branching programs. Our main result shows that nondeterminism can be more powerful than randomness for read-once branching programs. We present a ... more >>>

Branching programs (b.p.s) or binary decision diagrams are a general graph-based model of sequential computation. The 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. The restrictions based on the number of tests of variables during any computation ... more >>>

We show the following Reduction Lemma: any $\epsilon$-biased sample space with respect to (Boolean) linear tests is also $2\epsilon$-biased with respect to any system of independent linear tests. Combining this result with the previous constructions of $\epsilon$-biased sample space with respect to linear tests, we obtain the first efficient construction ... more >>>

We propose an information-theoretic approach to proving lower bounds on the size of branching programs (b.p.). The argument is based on Kraft-McMillan type inequalities for the average amount of uncertainty about (or entropy of) a given input during various stages of the computation. We first demonstrate the approach for read-once ... more >>>

Branching programs are a model for representing Boolean functions. For general branching programs, the satisfiability and nonequivalence tests are NP-complete. For read-once branching programs, which can test each variable at most once in each computation, the satisfiability test is trivial and there is also a probabilistic polynomial time test of ... more >>>

We obtain the first non-trivial time-space tradeoff lower bound for functions f:{0,1}^n ->{0,1} on general branching programs by exhibiting a Boolean function f that requires exponential size to be computed by any branching program of length cn, for some constant c>1. We also give the first separation result between the ... more >>>

Linear Transformed Ordered Binary Decision Diagrams (LTOBDDs) have been suggested as a generalization of OBDDs for the representation and manipulation of Boolean functions. Instead of variables as in the case of OBDDs parities of variables may be tested at the nodes of an LTOBDD. By this extension it is possible ... more >>>

A regular $(1,+k)$-branching program ($(1,+k)$-ReBP) is an ordinary branching program with the following restrictions: (i) along every consistent path at most $k$ variables are tested more than once, (ii) for each node $v$ on all paths from the source to $v$ the same set $X(v)\subseteq X$ of variables is tested, ... more >>>

We prove the first time-space lower bound tradeoffs for randomized computation of decision problems. The bounds hold even in the case that the computation is allowed to have arbitrary probability of error on a small fraction of inputs. Our techniques are an extension of those used by Ajtai in his ... more >>>

One of the great challenges of complexity theory is the problem of analyzing the dependence of the complexity of Boolean functions on the resources nondeterminism and randomness. So far, this problem could be solved only for very few models of computation. For so-called partitioned binary decision diagrams, which are a ... more >>>

This paper deals with the number of monochromatic combinatorial rectangles required to approximate a Boolean function on a constant fraction of all inputs, where each rectangle may be defined with respect to its own partition of the input variables. The main result of the paper is that the number of ... more >>>

We show that recognizing the $K_3$-freeness and $K_4$-freeness of graphs is hard, respectively, for two-player nondeterministic communication protocols with exponentially many partitions and for nondeterministic (syntactic) read-$s$ times branching programs. The key ingradient is a generalization of a coloring lemma, due to Papadimitriou and Sipser, which says that for every ... more >>>

Branching programs are a well-established computation model for Boolean functions, especially read-once branching programs have been studied intensively. Exponential lower bounds for deterministic and nondeterministic read-once branching programs are known for a long time. On the other hand, the problem of proving superpolynomial lower bounds for parity read-once branching programs ... more >>>

We present a new lower bound technique for two types of restricted Branching Programs (BPs), namely for read-once BPs (BP1s) with restricted amount of nondeterminism and for (1,+k)-BPs. For this technique, we introduce the notion of (strictly) k-wise l-mixed Boolean functions, which generalizes the concept of l-mixedness defined by Jukna ... more >>>

We prove upper and lower bounds on the power of quantum and stochastic branching programs of bounded width. We show any NC^1 language can be accepted exactly by a width-2 quantum branching program of polynomial length, in contrast to the classical case where width 5 is necessary unless \NC^1=\ACC. This ... more >>>

Branching programs are a well-established computation model for boolean functions, especially read-once branching programs (BP1s) have been studied intensively. A very simple function $f$ in $n^2$ variables is exhibited such that both the function $f$ and its negation $\neg f$ can be computed by $\Sigma^3_p$-circuits, the function $f$ has nondeterministic ... more >>>

It is well known that the hardest bit of integer multiplication is the middle bit, i.e. MUL_{n-1,n}. This paper contains several new results on its complexity. First, the size s of randomized read-k branching programs, or, equivalently, its space (log s) is investigated. A randomized algorithm for MUL_{n-1,n} with k=O(log ... more >>>

In this paper we propose the study of a new model of restricted branching programs which we call incremental branching programs. This is in line with the program proposed by Cook in 1974 as an approach for separating the class of problems solvable in logarithmic space from problems solvable in ... more >>>

The parallel complexity class NC^1 has many equivalent models such as polynomial size formulae and bounded width branching programs. Caussinus et al. \cite{CMTV} considered arithmetizations of two of these classes, #NC^1 and #BWBP. We further this study to include arithmetization of other classes. In particular, we show that counting paths ... more >>>

Functions in arithmetic NC1 are known to have equivalent constant width polynomial degree circuits, but the converse containment is unknown. In a partial answer to this question, we show that syntactic multilinear circuits of constant width and polynomial degree can be depth-reduced, though the resulting circuits need not be syntactic ... more >>>