Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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 >>>

TR07-011 | 19th December 2006
Bodo Manthey

On Approximating Restricted Cycle Covers

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 >>>

TR06-045 | 13th March 2006
Jan Arpe, Bodo Manthey

Approximability of Minimum AND-Circuits

Revisions: 1

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 >>>

TR05-063 | 24th June 2005
Bodo Manthey, Rüdiger Reischuk

Smoothed Analysis of the Height of Binary Search Trees

Revisions: 2

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 >>>

TR03-071 | 18th August 2003
Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey

Privacy in Non-Private Environments

Revisions: 1

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 >>>

TR03-009 | 3rd February 2003
Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey

Private Computation --- $k$-connected versus $1$-connected Networks

Revisions: 1

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 >>>

ISSN 1433-8092 | Imprint