Martin Sauerhoff

According to our database, Martin Sauerhoff authored at least 33 papers between 1994 and 2010.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2010

An asymptotically optimal lower bound on the OBDD size of the middle bit of multiplication for the pairwise ascending variable order.

Martin Sauerhoff

Discret. Appl. Math., 2010

Binary Decision Diagrams.

Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener, Yves Crama, Peter L. Hammer

Proceedings of the Boolean Models and Methods in Mathematics, 2010

2009

Applying Approximate Counting for Computing the Frequency Moments of Long Data Streams.

André Gronemeier, Martin Sauerhoff

Theory Comput. Syst., 2009

2006

Quantum vs. Classical Read-Once Branching Programs.

Martin Sauerhoff

Proceedings of the Complexity of Boolean Functions, 12.03. - 17.03.2006, 2006

2005

Quantum branching programs and space-bounded nonuniform quantum complexity.

Martin Sauerhoff, Detlef Sieling

Theor. Comput. Sci., 2005

2004

On multi-partition communication complexity.

Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger

Inf. Comput., 2004

2003

Approximation of boolean functions by combinatorial rectangles.

Martin Sauerhoff

Theor. Comput. Sci., 2003

The Power of Nondeterminism and Randomness for Oblivious Branching Programs.

Juraj Hromkovic, Martin Sauerhoff

Theory Comput. Syst., 2003

Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.

Martin Sauerhoff

J. Comput. Syst. Sci., 2003

Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions.

Martin Sauerhoff, Philipp Woelfel

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Randomness versus Nondeterminism for Read-Once and Read- k Branching Programs.

Martin Sauerhoff

Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

2002

On the Nonapproximability of Boolean Functions by OBDDs and Read-k-Times Branching Programs.

Beate Bollig, Martin Sauerhoff, Ingo Wegener

Inf. Comput., 2002

2001

On Multipartition Communication Complexity

Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger

Electron. Colloquium Comput. Complex., 2001

On the size of randomized OBDDs and read-once branching programs for k-stable functions.

Martin Sauerhoff

Comput. Complex., 2001

Randomized Branching Programs.

Martin Sauerhoff

Proceedings of the Stochastic Algorithms: Foundations and Applications, 2001

On the Non-Approximability of Boolean Functions by OBDDs and Read-K-Times Branching Programs.

Beate Bollig, Martin Sauerhoff, Ingo Wegener

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000

An Improved Hierarchy Result for Partitioned BDDs

Martin Sauerhoff

Electron. Colloquium Comput. Complex., 2000

Optimal ordered binary decision diagrams for read-once formulas.

Martin Sauerhoff, Ingo Wegener, Ralph Werchner

Discret. Appl. Math., 2000

Tradeoffs between Nondeterminism and Complexity for Communication Protocols and Branching Programs.

Juraj Hromkovic, Martin Sauerhoff

Proceedings of the STACS 2000, 2000

1999

Complexity theoretical results for randomized branching programs.

Martin Sauerhoff

PhD thesis, 1999

On the complexity of the hidden weighted bit function for various BDD models.

Beate Bollig, Martin Löbbing, Martin Sauerhoff, Ingo Wegener

RAIRO Theor. Informatics Appl., 1999

Relating Branching Program Size and Formula Size over the Full Binary Basis.

Martin Sauerhoff, Ingo Wegener, Ralph Werchner

Proceedings of the STACS 99, 1999

Komplexitätstheoretische Ergebnisse für Randomisierte Branchingprogramme.

Martin Sauerhoff

Proceedings of the Ausgezeichnete Informatikdissertationen 1999, 1999

Computing with Restricted Nondeterminism: The Dependence of the OBDD Size on the Number of Nondeterministic Variables.

Martin Sauerhoff

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1999

1998

Hierarchy Theorems for <i>k</i>OBDDs and <i>k</i>IBDDs.

Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener

Theor. Comput. Sci., 1998

The complexity of the inclusion operation on OFDD's.

Rolf Drechsler, Martin Sauerhoff, Detlef Sieling

IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 1998

Randomness and Nondeterminism are Incomparable for Read-Once Branching Programs

Martin Sauerhoff

Electron. Colloquium Comput. Complex., 1998

Lower Bounds for Randomized Read-k-Times Branching Programs (Extended Abstract).

Martin Sauerhoff

Proceedings of the STACS 98, 1998

1997

On Nondeterminism versus Randomness for Read-Once Branching Programs

Martin Sauerhoff

Electron. Colloquium Comput. Complex., 1997

A Lower Bound for Randomized Read-k-Times Branching Programs

Martin Sauerhoff

Electron. Colloquium Comput. Complex., 1997

1996

On the complexity of minimizing the OBDD size for incompletely specified functions.

Martin Sauerhoff, Ingo Wegener

IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 1996

Optimal Ordered Binary Decision Diagrams for Tree-like Circuits

Martin Sauerhoff, Ingo Wegener, Ralph Werchner

Electron. Colloquium Comput. Complex., 1996

1994

On the Power of Different Types of Restricted Branching Programs

Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener

Electron. Colloquium Comput. Complex., 1994