dblp.uni-trier.dewww.uni-trier.de

Martin Sauerhoff

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeer - CSB - Google - MSN - Yahoo
Home Page

2006
32EEMartin Sauerhoff: Quantum vs. Classical Read-Once Branching Programs. Complexity of Boolean Functions 2006
2005
31EEMartin Sauerhoff, Detlef Sieling: Quantum branching programs and space-bounded nonuniform quantum complexity. Theor. Comput. Sci. 334(1-3): 177-225 (2005)
2004
30EEPavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger: On multi-partition communication complexity. Inf. Comput. 194(1): 49-75 (2004)
2003
29EEMartin Sauerhoff: Randomness versus Nondeterminism for Read-Once and Read- k Branching Programs. STACS 2003: 307-318
28EEMartin Sauerhoff, Philipp Woelfel: Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions. STOC 2003: 186-195
27EEMartin Sauerhoff: Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines. J. Comput. Syst. Sci. 66(3): 473-495 (2003)
26EEMartin Sauerhoff: Approximation of boolean functions by combinatorial rectangles. Theor. Comput. Sci. 1-3(301): 45-78 (2003)
25EEJuraj Hromkovic, Martin Sauerhoff: The Power of Nondeterminism and Randomness for Oblivious Branching Programs. Theory Comput. Syst. 36(2): 159-182 (2003)
2002
24EEBeate Bollig, Martin Sauerhoff, Ingo Wegener: On the Nonapproximability of Boolean Functions by OBDDs and Read-k-Times Branching Programs. Inf. Comput. 178(1): 263-278 (2002)
2001
23EEBeate Bollig, Martin Sauerhoff, Ingo Wegener: On the Non-Approximability of Boolean Functions by OBDDs and Read-K-Times Branching Programs. IEEE Conference on Computational Complexity 2001: 172-183
22EEMartin Sauerhoff: Randomized Branching Programs. SAGA 2001: 65-72
21EEPavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger: On Multipartition Communication Complexity. STACS 2001: 206-217
20EEMartin Sauerhoff: On the size of randomized OBDDs and read-once branching programs for k-stable functions. Computational Complexity 10(2): 155-178 (2001)
19EEPavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger: On Multipartition Communication Complexity Electronic Colloquium on Computational Complexity (ECCC) 8(066): (2001)
2000
18EEJuraj Hromkovic, Martin Sauerhoff: Tradeoffs between Nondeterminism and Complexity for Communication Protocols and Branching Programs. STACS 2000: 145-156
17 Martin Sauerhoff, Ingo Wegener, Ralph Werchner: Optimal ordered binary decision diagrams for read-once formulas. Discrete Applied Mathematics 103(1-3): 237-258 (2000)
16EEMartin Sauerhoff: An Improved Hierarchy Result for Partitioned BDDs Electronic Colloquium on Computational Complexity (ECCC) 7(57): (2000)
15EEMartin Sauerhoff: Approximation of Boolean Functions by Combinatorial Rectangles Electronic Colloquium on Computational Complexity (ECCC) 7(58): (2000)
14EEMartin Sauerhoff: An Improved Hierarchy Result for Partitioned BDDs. Theory Comput. Syst. 33(4): 313-329 (2000)
1999
13EEMartin Sauerhoff: Computing with Restricted Nondeterminism: The Dependence of the OBDD Size on the Number of Nondeterministic Variables. FSTTCS 1999: 342-355
12EEMartin Sauerhoff: On the Size of Randomized OBDDs and Read-Once Branching Programs for k-Stable Functions. STACS 1999: 488-499
11EEMartin Sauerhoff, Ingo Wegener, Ralph Werchner: Relating Branching Program Size and Formula Size over the Full Binary Basis. STACS 1999: 57-67
10 Beate Bollig, Martin Löbbing, Martin Sauerhoff, Ingo Wegener: On the complexity of the hidden weighted bit function for various BDD models. ITA 33(2): 103-116 (1999)
1998
9 Martin Sauerhoff: Lower Bounds for Randomized Read-k-Times Branching Programs (Extended Abstract). STACS 1998: 105-115
8EEMartin Sauerhoff: Randomness and Nondeterminism are Incomparable for Read-Once Branching Programs Electronic Colloquium on Computational Complexity (ECCC) 5(18): (1998)
7EERolf Drechsler, Martin Sauerhoff, Detlef Sieling: The complexity of the inclusion operation on OFDD's. IEEE Trans. on CAD of Integrated Circuits and Systems 17(5): 457-459 (1998)
6EEBeate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener: Hierarchy Theorems for kOBDDs and kIBDDs. Theor. Comput. Sci. 205(1-2): 45-60 (1998)
1997
5EEMartin Sauerhoff: A Lower Bound for Randomized Read-k-Times Branching Programs Electronic Colloquium on Computational Complexity (ECCC) 4(19): (1997)
4EEMartin Sauerhoff: On Nondeterminism versus Randomness for Read-Once Branching Programs Electronic Colloquium on Computational Complexity (ECCC) 4(30): (1997)
1996
3EEMartin Sauerhoff, Ingo Wegener, Ralph Werchner: Optimal Ordered Binary Decision Diagrams for Tree-like Circuits Electronic Colloquium on Computational Complexity (ECCC) 3(22): (1996)
2EEMartin Sauerhoff, Ingo Wegener: On the complexity of minimizing the OBDD size for incompletely specified functions. IEEE Trans. on CAD of Integrated Circuits and Systems 15(11): 1435-1437 (1996)
1994
1EEBeate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener: On the Power of Different Types of Restricted Branching Programs Electronic Colloquium on Computational Complexity (ECCC) 1(26): (1994)

Coauthor Index

1Beate Bollig [1] [6] [10] [23] [24]
2Rolf Drechsler [7]
3Pavol Duris [19] [21] [30]
4Juraj Hromkovic [18] [19] [21] [25] [30]
5Stasys Jukna [19] [21] [30]
6Martin Löbbing [10]
7Georg Schnitger [19] [21] [30]
8Detlef Sieling [1] [6] [7] [31]
9Ingo Wegener [1] [2] [3] [6] [10] [11] [17] [23] [24]
10Ralph Werchner [3] [11] [17]
11Philipp Woelfel [28]

Copyright © Sun May 17 03:24:02 2009 by Michael Ley (ley@uni-trier.de)