Martin Sauerhoff

37 papers A* 1A 7Journal 23Unranked 3
YearRankTypeTitle / Venue / Authors
2010 J jnl
An asymptotically optimal lower bound on the OBDD size of the middle bit of multiplication for the pairwise ascending variable order.
Discret. Appl. Math.
Martin Sauerhoff
2010 — ch.
Binary Decision Diagrams.
Boolean Models and Methods
Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener, Yves Crama, Peter L. Hammer
2009 J jnl
Applying Approximate Counting for Computing the Frequency Moments of Long Data Streams.
Theory Comput. Syst.
André Gronemeier, Martin Sauerhoff
2006 — conf
Quantum vs. Classical Read-Once Branching Programs.
Complexity of Boolean Functions
Martin Sauerhoff
2005 J jnl
Quantum branching programs and space-bounded nonuniform quantum complexity.
Theor. Comput. Sci.
Martin Sauerhoff, Detlef Sieling
2004 J jnl
On multi-partition communication complexity.
Inf. Comput.
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger
2003 J jnl
Approximation of boolean functions by combinatorial rectangles.
Theor. Comput. Sci.
Martin Sauerhoff
2003 J jnl
Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
J. Comput. Syst. Sci.
Martin Sauerhoff
2003 A conf
Randomness versus Nondeterminism for Read-Once and Read- k Branching Programs.
STACS
Martin Sauerhoff
2003 J jnl
The Power of Nondeterminism and Randomness for Oblivious Branching Programs.
Theory Comput. Syst.
Juraj Hromkovic, Martin Sauerhoff
2003 A* conf
Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions.
STOC
Martin Sauerhoff, Philipp Woelfel
2002 J jnl
On the Nonapproximability of Boolean Functions by OBDDs and Read-k-Times Branching Programs.
Inf. Comput.
Beate Bollig, Martin Sauerhoff, Ingo Wegener
2001 J jnl
On Multipartition Communication Complexity
Electron. Colloquium Comput. Complex.
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger
2001 A conf
On Multipartition Communication Complexity.
STACS
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger
2001 A conf
On the Non-Approximability of Boolean Functions by OBDDs and Read-K-Times Branching Programs.
CCC
Beate Bollig, Martin Sauerhoff, Ingo Wegener
2001 J jnl
On the size of randomized OBDDs and read-once branching programs for k-stable functions.
Comput. Complex.
Martin Sauerhoff
2001 — conf
Randomized Branching Programs.
SAGA
Martin Sauerhoff
2000 J jnl
An Improved Hierarchy Result for Partitioned BDDs
Electron. Colloquium Comput. Complex.
Martin Sauerhoff
2000 J jnl
An Improved Hierarchy Result for Partitioned BDDs.
Theory Comput. Syst.
Martin Sauerhoff
2000 J jnl
Approximation of Boolean Functions by Combinatorial Rectangles
Electron. Colloquium Comput. Complex.
Martin Sauerhoff
2000 J jnl
Optimal ordered binary decision diagrams for read-once formulas.
Discret. Appl. Math.
Martin Sauerhoff, Ingo Wegener, Ralph Werchner
2000 A conf
Tradeoffs between Nondeterminism and Complexity for Communication Protocols and Branching Programs.
STACS
Juraj Hromkovic, Martin Sauerhoff
1999 — —
Complexity theoretical results for randomized branching programs.
Martin Sauerhoff
1999 — conf
Computing with Restricted Nondeterminism: The Dependence of the OBDD Size on the Number of Nondeterministic Variables.
FSTTCS
Martin Sauerhoff
1999 — ch.
Komplexitätstheoretische Ergebnisse für Randomisierte Branchingprogramme.
Ausgezeichnete Informatikdissertationen
Martin Sauerhoff
1999 A conf
On the Size of Randomized OBDDs and Read-Once Branching Programs for k-Stable Functions.
STACS
Martin Sauerhoff
1999 J jnl
On the complexity of the hidden weighted bit function for various BDD models.
RAIRO Theor. Informatics Appl.
Beate Bollig, Martin Löbbing, Martin Sauerhoff, Ingo Wegener
1999 A conf
Relating Branching Program Size and Formula Size over the Full Binary Basis.
STACS
Martin Sauerhoff, Ingo Wegener, Ralph Werchner
1998 J jnl
Hierarchy Theorems for
Theor. Comput. Sci.
Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener
1998 A conf
Lower Bounds for Randomized Read-k-Times Branching Programs (Extended Abstract).
STACS
Martin Sauerhoff
1998 J jnl
Randomness and Nondeterminism are Incomparable for Read-Once Branching Programs
Electron. Colloquium Comput. Complex.
Martin Sauerhoff
1998 J jnl
The complexity of the inclusion operation on OFDD's.
IEEE Trans. Comput. Aided Des. Integr. Circuits Syst.
Rolf Drechsler, Martin Sauerhoff, Detlef Sieling
1997 J jnl
A Lower Bound for Randomized Read-k-Times Branching Programs
Electron. Colloquium Comput. Complex.
Martin Sauerhoff
1997 J jnl
On Nondeterminism versus Randomness for Read-Once Branching Programs
Electron. Colloquium Comput. Complex.
Martin Sauerhoff
1996 J jnl
On the complexity of minimizing the OBDD size for incompletely specified functions.
IEEE Trans. Comput. Aided Des. Integr. Circuits Syst.
Martin Sauerhoff, Ingo Wegener
1996 J jnl
Optimal Ordered Binary Decision Diagrams for Tree-like Circuits
Electron. Colloquium Comput. Complex.
Martin Sauerhoff, Ingo Wegener, Ralph Werchner
1994 J jnl
On the Power of Different Types of Restricted Branching Programs
Electron. Colloquium Comput. Complex.
Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener