All reports by Author Andreas Jakoby:

__
TR11-128
| 21st September 2011
__

Michael Elberfeld, Andreas Jakoby, Till Tantau#### Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth

__
TR10-062
| 7th April 2010
__

Michael Elberfeld, Andreas Jakoby, Till Tantau#### Logspace Versions of the Theorems of Bodlaender and Courcelle

__
TR06-085
| 15th May 2006
__

Andreas Jakoby, Maciej Liskiewicz, Aleksander Madry#### Using Quantum Oblivious Transfer to Cheat Sensitive Quantum Bit Commitment

Revisions: 1

__
TR03-083
| 21st November 2003
__

Jan Arpe, Andreas Jakoby, Maciej Liskiewicz#### One-Way Communication Complexity of Symmetric Boolean Functions

__
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

__
TR02-021
| 11th April 2002
__

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk#### Space Efficient Algorithms for Directed Series-Parallel Graphs

__
TR01-090
| 28th November 2001
__

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk#### Dynamic Process Graphs and the Complexity of Scheduling

__
TR01-038
| 14th May 2001
__

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk#### Approximating Schedules for Dynamic Graphs Efficiently

Michael Elberfeld, Andreas Jakoby, Till Tantau

An algorithmic meta theorem for a logic and a class $C$ of structures states that all problems expressible in this logic can be solved efficiently for inputs from $C$. The prime example is Courcelle's Theorem, which states that monadic second-order (MSO) definable problems are linear-time solvable on graphs of bounded ... more >>>

Michael Elberfeld, Andreas Jakoby, Till Tantau

Bodlaender's Theorem states that for every $k$ there is a linear-time algorithm that decides whether an input graph has tree width~$k$ and, if so, computes a width-$k$ tree composition. Courcelle's Theorem builds on Bodlaender's Theorem and states that for every monadic second-order formula $\phi$ and for

every $k$ there is ...
more >>>

Andreas Jakoby, Maciej Liskiewicz, Aleksander Madry

It is well known that unconditionally secure bit commitment is impossible

even in the quantum world. In this paper a weak variant of quantum bit

commitment, introduced independently by Aharonov et al. and Hardy and Kent

is investigated. In this variant, the parties require some nonzero probability

more >>>

Jan Arpe, Andreas Jakoby, Maciej Liskiewicz

We study deterministic one-way communication complexity

of functions with Hankel communication matrices.

Some structural properties of such matrices are established

and applied to the one-way two-party communication complexity

of symmetric Boolean functions.

It is shown that the number of required communication bits

does not depend on ...
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 >>>

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk

The subclass of directed series-parallel graphs plays an important role in

computer science. Whether a given graph is series-parallel is a

well studied problem in algorithmic graph theory, for which fast sequential and

parallel algorithms have been developed in a sequence of papers.

Also methods are known to solve ...
more >>>

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk

In parallel and distributed computing scheduling low level tasks

on the available hardware is a fundamental problem.

Traditionally, one has assumed that the set of tasks to be executed

is known beforehand.

Then the scheduling constraints are given by a precedence graph.

Nodes represent the elementary tasks ...
more >>>

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk

A model for parallel and distributed programs, the dynamic process graph (DPG),

is investigated under graph-theoretic and complexity aspects.

Such graphs embed constructors for parallel programs,

synchronization mechanisms as well as conditional branches.

They are capable of representing all possible executions of a

parallel or distributed program ...
more >>>