Let $f$ be a Boolean function. Let $N(f)=\dnf(f)+\dnf(\neg f)$ be the sum of the minimum number of monomials in a disjunctive normal form for $f$ and $\neg f$. Let $p(f)$ be the minimum size of a partition of the Boolean cube into disjoint subcubes such that $f$ is constant on ... 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 >>>

Ordered binary decision diagrams (OBDDs) and their variants are motivated by the need to represent Boolean functions in applications. Research concerning these applications leads also to problems and results interesting from theoretical point of view. In this paper, methods from communication complexity and information theory are combined to prove that ... more >>>

There are Boolean functions such that almost all orderings of its variables yield an OBDD of polynomial size, but there are also some exceptional orderings, for which the size is exponential. We prove that for parity OBDDs the size for a random ordering and the size for the worst ordering ... 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 >>>

For any Boolean function $f$ let $L(f)$ be its formula size complexity in the basis $\{\land,\oplus,1\}$. For every $n$ and every $k\le n/2$, we describe a probabilistic distribution on formulas in the basis $\{\land,\oplus,1\}$ in some given set of $n$ variables and of the size at most $l(k)=4^k$. Let $p_{n,k}(f)$ ... more >>>

It is known that if a Boolean function f in n variables has a DNF and a CNF of size at most N then f also has a (deterministic) decision tree of size $\exp(O(\log n\log^2 N)$. We show that this simulation {\em cannot} be made polynomial: we exhibit explicit Boolean ... 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 >>>

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