All reports by Author Maciej Liskiewicz:

__
TR07-066
| 24th April 2007
__

Maciej Liskiewicz, Christian Hundt#### A Combinatorial Geometric Approach to Linear Image Matching

__
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

__
TR95-005
| 1st January 1995
__

Maciej Liskiewicz, Rüdiger Reischuk#### The Sublogarithmic Alternating Space World

Maciej Liskiewicz, Christian Hundt

The problem of image matching is to find for two given digital images $A$ and $B$

an admissible transformation that converts image $A$ as close as possible to $B$.

This problem becomes hard if the space of admissible transformations is too complex.

Consequently, in many real applications, like the ones ...
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 >>>

Maciej Liskiewicz, Rüdiger Reischuk

This paper tries to fully characterize the properties and relationships

of space classes defined by Turing machines that use less than

logarithmic space - may they be deterministic,

nondeterministic or alternating (DTM, NTM or ATM).

We provide several examples of specific languages ...
more >>>