All reports by Author Ingo Wegener:

__
TR07-049
| 1st June 2007
__

Beate Bollig, Niko Range, Ingo Wegener#### Exact OBDD Bounds for some Fundamental Functions

__
TR04-107
| 24th November 2004
__

Ingo Wegener, Philipp Woelfel#### New Results on the Complexity of the Middle Bit of Multiplication

Revisions: 1

__
TR04-089
| 26th October 2004
__

Ingo Wegener#### Simulated Annealing Beats Metropolis in Combinatorial Optimization

__
TR04-076
| 17th September 2004
__

Oliver Giel, Ingo Wegener#### Searching Randomly for Maximum Matchings

__
TR03-048
| 24th June 2003
__

Stefan Droste, Thomas Jansen, Ingo Wegener#### Upper and Lower Bounds for Randomized Search Heuristics in Black-Box Optimization

__
TR03-017
| 27th March 2003
__

Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener#### On Converting CNF to DNF

__
TR00-052
| 3rd July 2000
__

Beate Bollig, Ingo Wegener#### Approximability and Nonapproximability by Binary Decision Diagrams

__
TR99-048
| 7th December 1999
__

Beate Bollig, Ingo Wegener#### Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems

__
TR99-028
| 30th August 1999
__

Stefan Edelkamp, Ingo Wegener#### On the performance of WEAK-HEAPSORT

__
TR99-011
| 14th April 1999
__

Matthias Krause, Petr Savicky, Ingo Wegener#### Approximations by OBDDs and the variable ordering problem

__
TR97-023
| 3rd June 1997
__

S. Jukna, A. Razborov, Petr Savicky, Ingo Wegener#### On P versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs

__
TR96-061
| 27th November 1996
__

Ryuhei Uehara, Kensei Tsuchida, Ingo Wegener#### Optimal attribute-efficient learning of disjunction, parity, and threshold functions

__
TR96-022
| 15th March 1996
__

Martin Sauerhoff, Ingo Wegener, Ralph Werchner#### Optimal Ordered Binary Decision Diagrams for Tree-like Circuits

__
TR95-047
| 5th October 1995
__

Martin Loebbing, Ingo Wegener#### The Number of Knight's Tours Equals 33,439,123,484,294 -- Counting with Binary Decision Diagrams

__
TR95-042
| 14th September 1995
__

Beate Bollig, Ingo Wegener#### Read-once Projections and Formal Circuit Verification with Binary Decision Diagrams

__
TR94-026
| 12th December 1994
__

Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener#### On the Power of Different Types of Restricted Branching Programs

Beate Bollig, Niko Range, Ingo Wegener

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

Ingo Wegener, Philipp Woelfel

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

Ingo Wegener

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

Oliver Giel, Ingo Wegener

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

Stefan Droste, Thomas Jansen, Ingo Wegener

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

Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener

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

Beate Bollig, Ingo Wegener

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

Beate Bollig, Ingo Wegener

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

Stefan Edelkamp, Ingo Wegener

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

more >>>

Matthias Krause, Petr Savicky, Ingo Wegener

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

S. Jukna, A. Razborov, Petr Savicky, Ingo Wegener

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

Ryuhei Uehara, Kensei Tsuchida, Ingo Wegener

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

Martin Sauerhoff, Ingo Wegener, Ralph Werchner

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

Martin Loebbing, Ingo Wegener

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

Beate Bollig, Ingo Wegener

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

Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener

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