Author name cluster

Martin Sauerhoff

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

TCS Journal 2005 Journal Article

Quantum branching programs and space-bounded nonuniform quantum complexity

Martin Sauerhoff
Detlef Sieling

In this paper, the space complexity of non-uniform quantum algorithms is investigated using the model of quantum branching programs (QBPs). In order to clarify the relationship between QBPs and non-uniform quantum Turing machines, simulations between these two models are presented which allow to transfer upper and lower bound results. Exploiting additional insights about the connection between the running time and the precision of amplitudes, it is shown that non-uniform quantum Turing machines with algebraic amplitudes and QBPs with a suitable analogous set of amplitudes are equivalent in computational power if both models work with bounded or unbounded error. Furthermore, quantum ordered binary decision diagrams (QOBDDs) are considered, which are restricted QBPs that can be regarded as a non-uniform analog of one-way quantum finite automata. Upper and lower bounds are proved that allow a classification of the computational power of QOBDDs in comparison to usual deterministic and randomized variants of the model. Finally, an extension of QBPs is proposed where the performed unitary operation may depend on the result of a previous measurement. A simulation of randomized BPs by this generalized QBP model as well as exponential lower bounds for its ordered variant are presented.

Details DOI

I&C Journal 2004 Journal Article

On multi-partition communication complexity

Pavol Ďuriš
Juraj Hromkovič
Stasys Jukna
Martin Sauerhoff
Georg Schnitger

We study k-partition communication protocols, an extension of the standard two-party best-partition model to k input partitions. The main results are as follows. 1. A strong explicit hierarchy on the degree of non-obliviousness is established by proving that, using k +1 partitions instead of k may decrease the communication complexity from Θ (n) to Θ (log k). 2. Certain linear codes are hard for k-partition protocols even when k may be exponentially large (in the input size). On the other hand, one can show that all characteristic functions of linear codes are easy for randomized OBDDs. 3. It is proved that there are subfunctions of the triangle-freeness function and the function ⊕Clique 3, n that are hard for multi-partition protocols. As an application, strongly exponential lower bounds on the size of nondeterministic read-once branching programs for these functions are obtained, solving an open problem of Razborov [Proceedings of eighth FCT NCS 529, Springer, 1991, pp. 47–60].

Details DOI

TCS Journal 2003 Journal Article

Approximation of boolean functions by combinatorial rectangles

Martin Sauerhoff

This paper deals with the number of monochromatic combinatorial rectangles required to approximate a boolean function on a constant fraction of all inputs, where each rectangle may use its own partition of the input variables. The main result of the paper is that the number of rectangles required for the approximation of boolean functions in this model is very sensitive to the allowed error. There is an explicitly defined sequence of boolean functions f n on n variables such that f n has rectangle approximations with a constant number of rectangles and one-sided error 1 3 +o(1) or two-sided error 1 4 +o(1), but, on the other hand, f n requires exponentially many rectangles if the error bounds are decreased by an arbitrarily small constant. As applications of this result, the following separation results for read-once branching programs are obtained. The functions from the main result require only linear size for nondeterministic read-once branching programs and randomized read-once branching programs with two-sided error 1 3 +o(1), while randomized read-once branching programs with constant two-sided error smaller than 1 3 and unambiguous nondeterministic read-once branching programs require exponential size.

Details DOI

STOC Conference 2003 Conference Paper

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

Martin Sauerhoff
Philipp Woelfel

We prove exponential size lower bounds for nondeterministic and randomized read- k BPs as well as a time-space tradeoff lower bound for unrestricted, deterministic multi-way BPs computing the middle bit of integer multiplication. The lower bound for randomized read- k BPs is superpolynomial as long as the error probability is superpolynomially small. For polynomially small error, we have a polynomial upper bound on the size of approximating read once BPs for this function. The lower bounds follow from a more general result for the graphs of universal hash classes that is applicable to the graphs of arithmetic functions such as integer multiplication, convolution, and finite field multiplication.

Details

I&C Journal 2002 Journal Article

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

Beate Bollig
Martin Sauerhoff
Ingo Wegener

Branching programs are considered as a nonuniform model of computation in complexity theory as well as a data structure for boolean functions in several applications. In many applications (e. g. , verification), exact representations are required. For learning boolean functions f on the basis of classified examples, it is sufficient to produce the representation of a function g approximating f. This motivates the investigation of the size of the smallest branching program approximating f. Although several nonapproximability results are contained in the papers on randomized branching programs, these results often do not work for the uniform distribution (which is the most important one in applications). Here, the following nonapproximability results are presented. (1) It is proven that two simple and well-known functions from the branching program literature require exponential size to be approximated with respect to the uniform distribution by OBDDs, which are the most important type of branching programs in applications. (2) The first truly exponential lower bound on the size of approximating syntactic read-k-times branching programs with respect to the uniform distribution and error probability 1/2−2−Ω(n), n the input size, is shown. In order to improve upon the best previous results for error probabilities smaller than 1/3, a strong combinatorial lemma from a paper of Ajtai on linear-length branching programs is exploited.

Details DOI

TCS Journal 1998 Journal Article

Hierarchy theorems for kOBDDs and kIBDDs

Beate Bollig
Martin Sauerhoff
Detlef Sieling
Ingo Wegener

Almost the same types of restricted branching programs (or binary decision diagrams BDDs) are considered in complexity theory and in applications like hardware verification. These models are read-once branching programs (free BDDs) and certain types of oblivious branching programs (ordered and indexed BDDs with k layers). The complexity of the satisfiability problem for these restricted branching programs is investigated and tight hierarchy results are proved for the classes of functions representable by k layers of ordered or indexed BDDs of polynomial size.

Details DOI