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 monotone ... 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 programs, where $k\ge 2$. ... 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- (or \vee-)node with a fan-out ... 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 far, ... 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 depth ... 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 steps. A byproduct ... more >>>