Hauptinhalt

Complete list of publications in German.

Journal Papers

• Martin Sauerhoff (2009).
  On the entropy of models for the Web graph.
  Submitted.

• Martin Sauerhoff (2008).
  An asymptotically optimal lower bound on the OBDD size of the middle bit of multiplication for the pairwise ascending variable order.
  Submitted.

• André Gronemeier, Martin Sauerhoff (2007).
  Applying Approximate Counting for Computing the Frequency Moments of Long Data Streams.
  To appear in Theory of Computing Systems.

• Martin Sauerhoff, Detlef Sieling (2005).
  Quantum branching programs and space-bounded nonuniform quantum complexity.
  Theoretical Computer Science 334(1-3):177-225. (Preliminary version: quant-ph/0403164.)

• Pavol Ďuriš, Juraj Hromkovič, Stasys Jukna, Martin Sauerhoff, Georg Schnitger (2004).
  On Multi-Partition Communication Complexity.
  Information and Computation 194:49-75.

• Martin Sauerhoff (2003).
  Guess-and-verify versus Unrestricted Nondeterminism for OBDDs and One-Way Turing Machines.
  Journal of Computer and System Sciences 66(3):473-495.

• Juraj Hromkovič and Martin Sauerhoff (2003).
  On the Power of Nondeterminism and Randomness for Oblivious Branching Programs.
  Theory of Computing Systems 36:159-182.

• Martin Sauerhoff (2003).
  Approximation of Boolean Functions by Combinatorial Rectangles.
  Theoretical Computer Science 301:45-78.

• Beate Bollig, Martin Sauerhoff, Ingo Wegener (2002).
  On the Non-Approximability of Boolean Functions by OBDDs and Read-k-Times Branching Programs.
  Information and Computation 178:263-278.

• Martin Sauerhoff (2001).
  On the Size of Randomized OBDDs and Read-Once Branching Programs for k-Stable Functions.
  Computational Complexity 10:155-178.

• Martin Sauerhoff, Ingo Wegener, Ralph Werchner (2000).
  Optimal Ordered Binary Decision Diagrams for Read-Once Formulas.
  Discrete Applied Mathematics 103:237-258.

• Martin Sauerhoff (2000).
  An Improved Hierarchy Result for Partitioned BDDs.
  Theory of Computing Systems 33:313-329.

• Beate Bollig, Martin Löbbing, Martin Sauerhoff, Ingo Wegener (1999).
  On the Complexity of the Hidden Weighted Bit Function for Various BDD Models.
  Theoretical Informatics and Applications 33:103-115.

• Rolf Drechsler, Martin Sauerhoff, Detlef Sieling (1998).
  The Complexity of the Inclusion Operation on OFDDs.
  IEEE Trans. on Computer Aided Design 17(5):457-459.

• Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener (1998).
  Hierarchy Theorems for kOBDDs and kIBDDs.
  Theoretical Computer Science 205(1):45-60.

• Martin Sauerhoff, Ingo Wegener (1996).
  On the Complexity of Minimizing the OBDD Size for Incompletely Specified Functions.
  IEEE Trans. on Computer Aided Design 15(11):1435-1437.

Conference Papers

• Pavol Ďuriš, Juraj Hromkovič, Stasys Jukna, Martin Sauerhoff, Georg Schnitger (2001).
  On Multi-Partition Communication Complexity.
  In Proc. of 18th STACS, 206-217, LNCS 2010, Springer-Verlag.

• Martin Sauerhoff, Philipp Woelfel (2003).
  Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions.
  In Proc. of STOC 2003, 186-195.

• Martin Sauerhoff (2003).
  Randomness versus Nondeterminism for Read-Once and Read-k Branching Programs.
  In Proc. of 20th STACS, 307-318, LNCS 2607, Springer-Verlag.

• Juraj Hromkovič and Martin Sauerhoff (2000).
  Tradeoffs between Nondeterminism and Complexity for Communication Protocols and Branching Programs.
  In Proc. of 17th STACS, 145-156, LNCS 1770, Springer-Verlag.

• Beate Bollig, Martin Sauerhoff, Ingo Wegener (2001).
  On the Non-Approximability of Boolean Functions by OBDDs and Read-k-Times Branching Programs.
  In Proc. of 16th Conference on Computational Complexity, 172-187.

• Martin Sauerhoff (1999).
  The Dependence of the OBDD Size on the Number of Nondeterministic Variables.
  In Proc. of FST & TCS '99, 342-355, LNCS 1738, Springer-Verlag. Best paper award.

• Martin Sauerhoff (1999).
  On the Size of Randomized OBDDs and Read-Once Branching Programs for k-Stable Functions.
  In Proc. of 16th STACS, 488-499, LNCS 1563, Springer-Verlag.

• Martin Sauerhoff, Ingo Wegener, Ralph Werchner (1999).
  Relating Branching Program Size and Formula Size over the Full Binary Basis.
  In Proc. of 16th STACS, 57-67, LNCS 1563, Springer-Verlag.

• Martin Sauerhoff (1998).
  Lower Bounds for Randomized Read-k-Times Branching Programs.
  In Proc. of 15th STACS, 105-115, LNCS 1373, Springer-Verlag.

• Martin Sauerhoff, Ingo Wegener, Ralph Werchner (1996).
  Optimal Ordererd Binary Decision Diagrams for Fanout-free Circuits.
  In Proc. of the Synthesis and System Integration of Mixed Technologies (SASIMI), 197-204.

• Beate Bollig, Martin Löbbing, Martin Sauerhoff, Ingo Wegener (1995).
  Complexity Theoretical Aspects of OFDDs.
  In Proc. of IFIP WG 10.5 Workshop on Applications of the Reed-Muller Expansion in Circuit Design, 198-205.

Chapters in Monographs

• Beate Bollig, Martin Sauerhoff, Detlef Sieling und Ingo Wegener (2007).
  Binary decision diagrams. To appear in Boolean Functions, Volume II, Y. Crama and P. L. Hammer (Eds.), Cambridge University Press.

• Martin Sauerhoff (1999). Randomisierte Branchingprogramme (in German). In Ausgezeichnete Informatikdissertationen 1999, H. Fiedler et al. (Eds.), Teubner-Verlag.

• Beate Bollig, Martin Löbbing, Martin Sauerhoff und Ingo Wegener.
  Complexity theoretical aspects of OFDDs (1996). In Representation of Discrete Functions, T. Sasao (Ed.), Kluwer Academic Publishers.

Invited Conference Talk

Martin Sauerhoff (2001).
Randomized branching programs.
In Proc. of Stochastic Algorithms: Foundations and Applications (SAGA), LNCS 2264, 65-71. Springer.

Theses

• Martin Sauerhoff (2003).
  On the Resources Nondeterminism and Randomness for Branching Programs.
  Habilitationsschrift, Fachbereich Informatik, Universität Dortmund.

• Martin Sauerhoff (1999).
  Complexity Theoretical Results for Randomized Branching Programs.
  Ph. D. Dissertation, Fachbereich Informatik, Universität Dortmund. Shaker.

• M. Sauerhoff (1993). Effiziente Algorithmen für kBDDs (in German). Diploma Thesis, Universität Dortmund.

Technical Reports