The model of span programs is a linear algebraic model of
computation. Lower bounds for span programs imply lower bounds for
contact schemes, symmetric branching programs and for formula size.
Monotone span programs correspond also to linear secret-sharing schemes.
We present a new technique for proving lower bounds for ... more >>>

In this paper, we are concerned with randomized OBDDs and randomized
read-k-times branching programs. We present an example of a Boolean
function which has polynomial size randomized OBDDs with small,
one-sided error, but only non-deterministic read-once branching
programs of exponential size. Furthermore, we discuss a lower bound
technique for randomized ... more >>>

Our computational model is a random access machine with $n$
read only input registers each containing $ c \log n$ bits of
information and a read and write memory. We measure the time by the
number of accesses to the input registers. We show that for all $k$
there is ... more >>>

We prove that for all positive integer $k$ and for all
sufficiently small $\epsilon >0$ if $n$ is sufficiently large
then there is no Boolean (or $2$-way) branching program of size
less than $2^{\epsilon n}$ which for all inputs
$X\subseteq \lbrace 0,1,...,n-1\rbrace $ computes in time $kn$
the parity of ... more >>>

Some operations over Boolean functions are considered. It is shown that
the operation of the geometrical projection and the operation of the
monotone extension can increase the complexity of Boolean functions for
formulas in each finite basis, for switching networks, for branching
programs, and read-$k$-times branching ... more >>>

Restricted branching programs are considered in complexity theory in
order to study the space complexity of sequential computations and
in applications as a data structure for Boolean functions. In this
paper (\oplus,k)-branching programs and (\vee,k)-branching
programs are considered, i.e., branching programs starting with a
\oplus- ... more >>>

Restricted branching programs are considered by the investigation
of relationships between complexity classes of Boolean functions.
Read-once ordered branching programs (or OBDDs) form the most restricted class
of this computation model.
Since the problem of proving exponential lower bounds on the complexity
for general probabilistic OBDDs is open so ... more >>>

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

In this paper we give a direct proof of $N_0=N_0^\prime$, i.e., the equivalence of
uniform $NC^1$ based on different recursion principles: one is OR-AND complete
binary tree (in depth $\log n$) and the other is the recursion on notation with value
bounded in $[0,k]$ and $|x|(=n)$ many ... more >>>

We consider so-called ``incremental'' dynamic programming (DP) algorithms, and are interested in the number of subproblems produced by them. The standard DP algorithm for the n-dimensional Knapsack problem is incremental, and produces nK subproblems, where K is the capacity of the knapsack. We show that any incremental algorithm for this ... more >>>