- Maciej Liskiewicz, Rüdiger Reischuk:
The Complexity World below Logarithmic Space.
Technischer Bericht SIIM-TR-A-95-07,
Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck,
1995.
Postscript anzeigen | Zusammenfassung anzeigen
We investigate space complexity classes defined by
Turing machines that use less than logarithmic space.
Because of the limited counting ability of such machines
most of the standard simulation techniques do not work for
sublogarithmic space classes.
However, machines with such little space may still be quite powerful.
Therefore, it was not obvious how to obtain analogs for inclusion and
separation results known for classes above logspace.
We review known facts about the sublogarithmic space world
and present several new results, which
show that these classes really behave differently.
For example, certain closure properties do not hold.
The restricted power of these machines makes it possible to prove explicit
separations -- even for alternating complexity classes --
by combinatorial arguments and to obtain a hierarchy of
non-relativized complexity classes without any unproven assumption.
We will also discuss upward and downward translation issues.
Finally, these complexity classes are related to other classes within P,
in particular to context-free languages.
- Maciej Liskiewicz, Rüdiger Reischuk:
The Sublogarithmic Alternating Space World.
Technischer Bericht SIIM-TR-A-95-01,
Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck,
1995.
Postscript anzeigen | Zusammenfassung anzeigen
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 and show that such machines
are unable to accept these languages.
The basic proof method is a nontrivial extension of the
1^n -> 1^{n+n!} technique to alternating TMs.
Let \llog denote the logarithmic function \log iterated twice,
and Sigma_k Space(S), Pi_k Space (S) be the complexity classes defined
by S-space-bounded ATMs that alternate at most k-1 times and
start in an existential, resp.~universal state.
Our first result shows that for each k > 1 the sets
Sigma_k Space(llog) \ Pi_k Space (o(log)) and
Pi_k Space(llog) \ Sigma_k Space (o(log))
are both not empty. This implies that for each S in the intersection of
Omega(llog) and o(log )
Sigma_1 Space(S), Sigma_2 Space(S), Sigma_3 Space(S) .. ..
form an infinite hierarchy.
Furthermore, this separation is extended to space classes defined
by ATMs with a nonconstant alternation bound A provided that
the product A * S grows sublogarithmically.
These lower bounds can also be used to show that basic closure
properties do not hold for such classes. We obtain
that for any S in Omega(llog) intersection o(log) and all k>1
\Sigma_k Space (S) and \Pi_k Space (S) are not
closed under complementation and concatenation.
Moreover, \Sigma_k Space (S) is not closed under intersection,
and \Pi_k Space (S) is not closed under union.
It is also shown that ATMs recognizing bounded languages can always be
guaranteed to halt. For the class of Z--bounded languages with
Z <= \exp S we obtain the equality
co-Sigma_k Space(S) = Pi_k Space (S) .
Finally, for sublogarithmic bounded ATMs we give a separation between
the weak and strong space measure, and prove a logarithmic lower space
bound for the recognition of nonregular context-free languages.
Key words:
space complexity, sublogarithmic complexity bounds,
alternating Turing machines, halting computations,
complementation of languages,
complexity hierachies, closure properties,
context-free languages, bounded languages.
AMS(MOS) subject classifications: 68Q05, 68Q10, 68Q25, 68Q45
Preliminary versions of these results have been presented at the
10. GI-AFCET Symposium on Theoretical Aspects of Computer Science,
W"urzburg, 1993,
and at the 9. IEEE-SIGACT-EATCS Symposium on Structure in
Complexity Theory, Amsterdam, 1994.
A final version will appear in SIAM Journal on Computing.
- Maciej Liskiewicz, Rüdiger Reischuk:
Separating Small Space Complexity Classes of Stochastic Turing Machines.
Technischer Bericht SIIM-TR-A-96-17,
Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck,
1996.
Postscript anzeigen | Zusammenfassung anzeigen
Stochastic Turing machines are Turing machines that can perform
nondeterministic and probabilistic moves.
Such devices are also called games against nature, Arthur-Merlin games,
or interactive proof systems with public coins.
We investigate stochastic machines
with space ressources between constant and logarithmic size
and constant or sublinear bounds on the number of alternations
between nondeterministic and probabilistic moves.
Separation results are proven for the corresponding complexity classes
by showing the inclusion, resp.~noninclusion of certain languages.
The lower bounds hold without any restriction on the run time
and will follow from more general combinatorial properties.
These results imply an infinite hierarchy with linear distance
based on the number of alternations.
The separations are obtained by extending and improving lower bound techniques
developed for probabilistic automata and stochastic machines by which
previously the lower levels have been separated, resp.~a hierarchy with
exponential distance has been shown.
Furthermore, we establish a hierarchy for stochastic Turing machines
with arbitrary small nonconstant space bounds.
COMMENTS: extends Technical Report A-96-08
- Maciej Liskiewicz, Rüdiger Reischuk:
Space Bounds for Interactive Proof Systems with Public Coins and Bounded Number of Rounds.
Technischer Bericht SIIM-TR-A-96-08,
Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck,
1996.
Postscript anzeigen | Zusammenfassung anzeigen
This paper studies interactive proofs, resp. Arthur-Merlin games
with a sublogarithmic space-bounded verifier.
We provide examples of specific languages and show that such systems
are unable to accept these languages. As a consequence, a new separation
is obtained for the complexity classes on the second
level of the round/alternation hierarchy.
- Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
Scheduling Dynamic Graphs.
Technischer Bericht SIIM-TR-A-98-07,
Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck,
1998.
Postscript anzeigen | Zusammenfassung anzeigen
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 and edges the dependencies among tasks. This static approach is not
appropriate in situations where the set of tasks is not known exactly in
advance, for example, when different options how to continue a program may
be granted.
In this paper a new model for parallel and distributed programs, the dynamic
process graph will be introduced, which represents all possible executions of
a program in a compact way. The size of this representation is small -- in
many cases only logarithmically with respect to the size of any execution.
An important feature of our model is that unlike precedence graphs, the
encoded executions are directed acyclic graphs having a "regular" structure
that is typical of parallel programs. Dynamic process graphs embed
constructors for parallel programs, synchronization mechanisms as well as
conditional branches. With respect to such a compact representation we
investigate the complexity of different aspects of the scheduling problem:
the question whether a legal schedule exists at all and how to find an
optimal schedule. Our analysis takes into account communication delays
between processors exchanging data.
Precise characterization of the computational complexity of various variants
of this compact scheduling problem will be given in this paper. The results
range from easy, that is NL-complete, to very hard, namely NEXPTIME-complete.
- Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
Space Efficient Algorithms for Series-Parallel Graphs.
Technischer Bericht SIIM-TR-A-00-17,
Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck,
2000.
Postscript anzeigen | Zusammenfassung anzeigen
The subclass of directed series-parallel graphs plays an important role in
computer science. To determine whether a graph is series-parallel is a
well studied problem in algorithmic graph theory. Fast sequential and
parallel algorithms for this problem have been developed in a sequence
of papers. For series-parallel graphs methods are also known to solve
the reachability and the decomposition problem time efficiently.
However, no dedicated results have been obtained for the space complexity
of these problems -- the topic of this paper.
For this special class of graphs, we develop deterministic algorithms
for the recognition, reachability, decomposition and the path counting
problem that use only logarithmic space. Since for arbitrary directed
graphs reachability and path counting are believed not to be solvable
in log-space the main contribution of this work are novel deterministic
path finding routines that work correctly in series-parallel graphs,
and a new characterization of series-parallel graphs by forbidden subgraphs.
We then sketch how these results can be generalised to extension of
the series-parallel graph family: to graphs with multiple sources or multiple
sinks and to the class of minimal vertex series-parallel graphs.
It it also shown that the space bounds are best possible,
i.e. the decision problems are L-complete with respect to AC-reductions.
Finally, we discuss implications of theses small space bounds for
the parallel time complexity of series-parallel graphs.
- Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
The Expressive Power and Complexity of Dynamic Process Graphs.
Technischer Bericht SIIM-TR-A-00-07,
Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck,
2000.
Postscript anzeigen | Zusammenfassung anzeigen
A model for parallel and distributed programs, the dynamic process graph,
is investigated under graph-theoretic and complexity aspects. Such graphs
are capable of representing all possible executions of a parallel or
distributed program in a very compact way. The size of this representation
is small -- in many cases only logarithmic with respect to the size of any
execution of the program. An important feature of this model is that
the encoded executions are directed acyclic graphs with a regular structure,
which is typical of parallel programs, and that it embeds constructors for
parallel programs, synchronization mechanisms as well as conditional branches.
In a previous paper we have analysed the expressive power of the general
model and various restrictions. Furthermore, from an algorithmic point
of view it is important to decide whether a given dynamic process graph can
be executed correctly and to estimate the minimal deadline given enough
parallelism. Our model takes into account communication delays between
processors when exchanging data.
In this paper we study a variant with output restriction. It is appropriate
in many situations, but its expressive power has not been known exactly.
First, we investigate structural properties of the executions of such dynamic
process graphs G. A natural graph-theoretic conjecture that executions must
always split into components isomorphic to subgraphs of G turns out to be
wrong. We are able to establish a weaker property. This implies a quadratic
bound on the maximal deadline in contrast to the general case, where
the execution time may be exponential. However, we show that the problem
to determine the minimal deadline is still intractable, namely this problem
is NEXPTIME-complete as is the general case. The lower bound is obtained by
showing that this kind of dynamic process graphs can represent certain
Boolean formulas in a highly succinct way.
This is an extended abstract to be presented at 26th International Workshop
on Graph-Theoretic Concepts in Computer Science, Konstanz, Germany, 2000.
- Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
Dynamic Process Graphs and the Complexity of Scheduling.
Technischer Bericht SIIM-TR-A-00-02,
Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck,
2002.
Postscript anzeigen | Zusammenfassung anzeigen
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 and edges the dependencies among
tasks. This static approach is not appropriate in situations where the
set of tasks is not known exactly in advance, for example, when different
options how to continue a program may be granted.
In this paper a new model for parallel and distributed programs, the dynamic
process graph, will be introduced, which represents all possible executions
of a program in a compact way. The size of this representation is small -- in
many cases only logarithmically with respect to the size of any execution.
An important feature of our model is that the encoded executions are directed
acyclic graphs having a 'regular' structure that is typical of parallel
programs.
Dynamic process graphs embed constructors for parallel programs,
synchronization mechanisms as well as conditional branches. With respect
to such a compact representation we investigate the complexity of different
aspects of the scheduling problem: the question whether a legal schedule
exists at all and how to find an optimal schedule. Our analysis takes into
account communication delays between processors exchanging data.
Precise characterization of the computational complexity of various variants
of this compact scheduling problem will be given in this paper. The results
range from easy, that is NL-complete, to very hard, namely NEXPTIME-complete.
This is a revised and complete version of results discussed in TR A-98-07.
An extended abstract of this paper has been presented at 16th International
Symposium on Theoretical Aspects of Computer Science, Trier, Germany, 1999.
- Maciej Liskiewicz, Rüdiger Reischuk, Ulrich Wölfel:
Grey-Box Steganography.
Technischer Bericht SIIM-TR-A-09-03,
Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck,
2009.
PDF anzeigen | Zusammenfassung anzeigen
In Steganography secret messages are encoded into unsuspicious covertexts such that an
adversary cannot distinguish the resulting stegotexts from original covertexts. To accomplish their respective tasks, encoder and adversary need information about the covertext distribution. In previous analyses, the knowledge about the covertext channel was unbalanced: while the adversary had full knowledge, the encoder could only query a black-box sampling oracle. In such a situation, the only general steganographic method known is rejection sampling, for which the sampling complexity has been shown to be exponential in the message length. To overcome this somewhat unrealistic scenario
and to get finer-grained security analyses, we propose a new model, called grey-box steganography. Here, the encoder starts with at least some partial knowledge about the type of covertext channel. Using the sampling oracle, he first uses machine learning techniques to learn the covertext distribution and then tries to actively construct a suitable stegotext – either by modifying a covertext or by creating a new one. The efficiency of grey-box steganography depends on the learning complexity of the concept class for the covertext channel, the efficiency of membership tests, and the complexity of the modification
procedure. We will give examples showing that this finer-grained distinction provides more insight and helps constructing efficient stegosystems that are provably secure against chosen hiddentext attacks. This way we can also easily model semantic steganography.
- Sebastian Berndt, Maciej Liskiewicz:
On the Gold Standard for Security of Universal Steganography.
Technischer Bericht 106,
IACR Cryptology ePrint Archive,
2018.
Website anzeigen - Benito van der Zander, Maciej Liskiewicz, Johannes Textor:
Separators and adjustment sets in causal graphs: Complete criteria and an algorithmic framework.
Technischer Bericht arXiv:1803.00116 (2018),
arXiv preprint,
2018.
PDF anzeigen - Martin R. Schuster, Maciej Liskiewicz:
New Abilities and Limitations of Spectral Graph Bisection.
Technischer Bericht 1701.01337,
arXiv,
2017.
Website anzeigen | Zusammenfassung anzeigen
Spectral based heuristics belong to well-known commonly used methods which determines provably minimal graph bisection or outputs "fail" when the optimality cannot be certified. In this paper we focus on Boppana's algorithm which belongs to one of the most prominent methods of this type. It is well known that the algorithm works well in the random \emph{planted bisection model} -- the standard class of graphs for analysis minimum bisection and relevant problems. In 2001 Feige and Kilian posed the question if Boppana's algorithm works well in the semirandom model by Blum and Spencer. In our paper we answer this question affirmatively. We show also that the algorithm achieves similar performance on graph classes which extend the semirandom model.
Since the behavior of Boppana's algorithm on the semirandom graphs remained unknown, Feige and Kilian proposed a new semidefinite programming (SDP) based approach and proved that it works on this model. The relationship between the performance of the SDP based algorithm and Boppana's approach was left as an open problem. In this paper we solve the problem in a complete way by proving that the bisection algorithm of Feige and Kilian provides exactly the same results as Boppana's algorithm. As a consequence we get that Boppana's algorithm achieves the optimal threshold for exact cluster recovery in the \emph{stochastic block model}. On the other hand we prove some limitations of Boppana's approach: we show that if the density difference on the parameters of the planted bisection model is too small then the algorithm fails with high probability in the model.