All reports by Author Philipp Woelfel:

__
TR04-107
| 24th November 2004
__

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

Revisions: 1

__
TR01-101
| 14th December 2001
__

Philipp Woelfel#### A Lower Bound Technique for Restricted Branching Programs and Applications

__
TR01-073
| 24th October 2001
__

Beate Bollig, Philipp Woelfel, Stephan Waack#### Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication

Revisions: 1

__
TR00-046
| 19th June 2000
__

Philipp Woelfel#### New Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing

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

Philipp Woelfel

We present a new lower bound technique for two types of restricted

Branching Programs (BPs), namely for read-once BPs (BP1s) with

restricted amount of nondeterminism and for (1,+k)-BPs. For this

technique, we introduce the notion of (strictly) k-wise l-mixed

Boolean functions, which generalizes the concept of l-mixedness ...
more >>>

Beate Bollig, Philipp Woelfel, Stephan Waack

Branching programs are a well-established computation model

for Boolean functions, especially read-once branching programs

have been studied intensively. Exponential lower bounds for

deterministic and nondeterministic read-once branching programs

are known for a long time. On the other hand, the problem of

proving superpolynomial lower bounds ...
more >>>

Philipp Woelfel

Ordered binary decision diagrams (OBDDs) belong to the most important

representation types for Boolean functions. Although they allow

important operations such as satisfiability test and equality test to

be performed efficiently, their limitation lies in the fact, that they

may require exponential size for important functions. Bryant ...
more >>>