Ordered binary decision diagrams (OBDDs) are nowadays the most common dynamic data structure or representation type for Boolean functions. Among the many areas of application are verification, model checking, computer aided design, relational algebra, and symbolic graph algorithms. Although many even exponential lower bounds on the OBDD size of Boolean ... 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 >>>

The Metropolis algorithm is simulated annealing with a fixed temperature.Surprisingly enough, many problems cannot be solved more efficiently by simulated annealing than by the Metropolis algorithm with the best temperature. The problem of finding a natural example (artificial examples are known) where simulated annealing outperforms the Metropolis algorithm for all ... more >>>

Many real-world optimization problems in, e.g., engineering or biology have the property that not much is known about the function to be optimized. This excludes the application of problem-specific algorithms. Simple randomized search heuristics are then used with surprisingly good results. In order to understand the working principles behind such ... more >>>

Randomized search heuristics like local search, simulated annealing or all kinds of evolutionary algorithms have many applications. However, for most problems the best worst-case expected run times are achieved by more problem-specific algorithms. This raises the question about the limits of general randomized search heuristics. Here a framework called black-box ... more >>>

The best-known representations of boolean functions f are those of disjunctions of terms (DNFs) and as conjuctions of clauses (CNFs). It is convenient to define the DNF size of f as the minimal number of terms in a DNF representing f and the CNF size as the minimal number of ... more >>>

Many BDD (binary decision diagram) models are motivated by CAD applications and have led to complexity theoretical problems and results. Motivated by applications in genetic programming Krause, Savick\'y, and Wegener (1999) have shown that for the inner product function IP$_n$ and the direct storage access function DSA$_n$ all functions which ... more >>>

Ordered binary decision diagrams (OBDDs) are nowadays the most common dynamic data structure or representation type for Boolean functions. Among the many areas of application are verification, model checking, and computer aided design. For many functions it is easy to estimate the OBDD size but asymptotically optimal bounds are only ... more >>>

Dutton presents a further HEAPSORT variant called WEAK-HEAPSORT which also contains a new data structure for priority queues. The sorting algorithm and the underlying data structure ara analyzed showing that WEAK-HEAPSORT is the best HEAPSORT variant and that it has a lot of nice properties. It is shown that the ... 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 >>>

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

Decision trees are a very general computation model. Here the problem is to identify a Boolean function $f$ out of a given set of Boolean functions $F$ by asking for the value of $f$ at adaptively chosen inputs. For classes $F$ consisting of functions which may be obtained from one ... more >>>

Many Boolean functions have short representations by OBDDs (ordered binary decision diagrams) if appropriate variable orderings are used. For tree-like circuits, which may contain EXOR-gates, it is proved that some depth first traversal leads to an optimal variable ordering. Moreover, an optimal variable ordering and the resulting OBDD can be ... more >>>

An increasing number of results in graph theory, combinatorics and theoretical computer science is obtained with the help of computers, e.g. the proof of the Four Colours Theorem or the computation of certain Ramsey numbers. Binary decision diagrams, known as tools in hardware verification and computer-aided design, are used here ... more >>>

Computational complexity is concerned with the complexity of solving problems and computing functions and not with the complexity of verifying circuit designs. The importance of formal circuit verification is evident. Therefore, a framework of a complexity theory for formal circuit verification with binary decision diagrams is developed. This theory is ... more >>>

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