All reports by Author Bodo Manthey:

__
TR07-039
| 27th March 2007
__

Bodo Manthey, Till Tantau#### Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise

Revisions: 1

__
TR07-011
| 19th December 2006
__

Bodo Manthey#### On Approximating Restricted Cycle Covers

__
TR06-045
| 13th March 2006
__

Jan Arpe, Bodo Manthey#### Approximability of Minimum AND-Circuits

Revisions: 1

__
TR05-063
| 24th June 2005
__

Bodo Manthey, Rüdiger Reischuk#### Smoothed Analysis of the Height of Binary Search Trees

Revisions: 2

__
TR03-071
| 18th August 2003
__

Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey#### Privacy in Non-Private Environments

Revisions: 1

__
TR03-009
| 3rd February 2003
__

Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey#### Private Computation --- $k$-connected versus $1$-connected Networks

Revisions: 1

Bodo Manthey, Till Tantau

Binary search trees are a fundamental data structure and their height

plays a key role in the analysis of divide-and-conquer algorithms like

quicksort. Their worst-case height is linear; their average height,

whose exact value is one of the best-studied problems in average-case

complexity, is logarithmic. We analyze their smoothed height ...
more >>>

Bodo Manthey

A cycle cover of a graph is a set of cycles such that every vertex is

part of exactly one cycle. An L-cycle cover is a cycle cover in which

the length of every cycle is in the set L. The weight of a cycle cover

of an edge-weighted graph ...
more >>>

Jan Arpe, Bodo Manthey

Given a set of monomials, the Minimum AND-Circuit problem asks for a

circuit that computes these monomials using AND-gates of fan-in two and

being of minimum size. We prove that the problem is not polynomial time

approximable within a factor of less than 1.0051 unless P = NP, even if

more >>>

Bodo Manthey, Rüdiger Reischuk

Binary search trees are one of the most fundamental data structures. While the

height of such a tree may be linear in the worst case, the average height with

respect to the uniform distribution is only logarithmic. The exact value is one

of the best studied problems in average case ...
more >>>

Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey

We study private computations in information-theoretical settings on

networks that are not 2-connected. Non-2-connected networks are

``non-private'' in the sense that most functions cannot privately be

computed on such networks. We relax the notion of privacy by

introducing lossy private protocols, which generalize private

protocols. We measure the information each ...
more >>>

Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey

We study the role of connectivity of communication networks in private

computations under information theoretic settings. It will be shown that

some functions can be computed by private protocols even if the

underlying network is 1-connected but not 2-connected. Then we give a

complete characterisation of non-degenerate functions that can ...
more >>>