- Max Bannach, Till Tantau:
Parallel Multivariate Meta-Theorems.
In Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC 2016), LIPIcs,
2016.
Go to website | Show PDF | Show abstract
Fixed-parameter tractability is based on the observation that many hard problems become tractable even on large inputs as long as certain input parameters are small. Originally, ``tractable'' just meant ``solvable in polynomial time,'' but especially modern hardware raises the question of whether we can also achieve ``solvable in polylogarithmic parallel time.'' A framework for this study of \emph{parallel fixed-parameter tractability} is available and a number of isolated algorithmic results have been obtained in recent years, but one of the unifying core tools of classical FPT theory has been missing: algorithmic meta-theorems. We establish two such theorems by giving new upper bounds on the circuit depth necessary to solve the model checking problem for monadic second-order logic, once parameterized by the tree width and the formula (this is a parallel version of Courcelle's Theorem) and once by the tree depth and the formula. For our proofs we refine the analysis of earlier algorithms, especially of Bodlaender's, but also need to add new ideas, especially in the context where the parallel runtime is bounded by a function of the parameter and does not depend on the length of the input.
- Sebastian Berndt, Maciej Liskiewicz:
Hard Communication Channels for Steganography.
In The 27th International Symposium on Algorithms and Computation (ISAAC 2016), ISBN 978-3-95977-026-2, LIPICS Vol. 64, Schloss Dagstuhl-Leibniz-Zentrum für Informatik,
2016.
Go to website | Show abstract
This paper considers steganography -- the concept of hiding
the presence of secret messages in legal communications --
in the computational setting and its relation to cryptography.
Very recently the first (non-polynomial time) steganographic protocol
has been shown which, for any communication channel, is provably secure,
reliable, and has nearly optimal bandwidth. The security is
unconditional, i.e. it does not rely on any unproven
complexity-theoretic assumption. This disproves the claim that the
existence of one-way functions and access to a communication channel
oracle are both necessary and sufficient conditions for the existence of
secure steganography in the sense that secure and reliable steganography
exists independently of the existence of one-way functions.
In this paper, we prove that this equivalence also
does not hold in the more realistic setting, where the
stegosystem is polynomial time bounded. We prove this by constructing
(a) a channel for which secure steganography exists if and only if one-way
functions exist and (b) another channel such that secure steganography
implies that no one-way functions exist. We therefore show that
security-preserving reductions between cryptography and
steganography need to be treated very carefully.
- Sebastian Berndt, Maciej Liskiewicz:
Provable Secure Universal Steganography of Optimal Rate.
In Proceedings of the 4rd ACM Workshop on Information Hiding and Multimedia Security, IH&MMSec 2016, Vigo, Spain, June 20 - 22, 2016, pp. 387-394.
ACM (Awarded Best Student Paper),
2016.
Go to website | Show abstract
We present the first complexity-theoretic secure steganographic protocol which, for any communication channel, is provably secure, reliable, and has nearly optimal bandwidth. Our system is unconditionally secure, i.e. our proof does not rely on any unproven complexity-theoretic assumption, like e.g. the existence of one-way functions. This disproves the claim that the existence of one-way functions and access to a communication channel oracle are both necessary and sufficient conditions for the existence of secure steganography, in the sense that secure and reliable steganography exists independently of the existence of one-way functions.
- Sebastian Berndt, Rüdiger Reischuk:
Steganography Based on Pattern Languages.
In Language and Automata Theory and Applications, 10th International Conference LATA 2016 Prague, Czech Republic, March 14-18, 2016, Volume Volume 9618 of Lecture Notes in Computer Science (LNCS), pp. 387-399.
Springer,
2016.
Go to website | Show abstract
In order to transmit secret information, such that this transmission cannot be
detected, steganography needs a channel, a set of strings with some distribution that occur in an ordinary communication.
The elements of such a language or concept are called coverdocuments.
The question how to design secure stegosystems for natural classes
of languages is investigated for pattern languages.
We present a randomized modification scheme for strings of a pattern
language that can reliably encode arbitrary messages and is almost
undetectable.
- Malte Skambath, Till Tantau:
Offline Drawing of Dynamic Trees: Algorithmics and Document Integration.
In GD 2016: Graph Drawing and Network Visualization, Volume 9801 of LNCS, pp. 572-586.
Springer,
2016.
Go to website | Show abstract
While the algorithmic drawing of static trees is well-understood and well-supported by software tools, creating animations depicting how a tree changes over time is currently difficult: software support, if available at all, is not integrated into a document production workflow and algorithmic approaches only rarely take temporal information into consideration. During the production of a presentation or a paper, most users will visualize how, say, a search tree evolves over time by manually drawing a sequence of trees. We present an extension of the popular Open image in new window typesetting system that allows users to specify dynamic trees inside their documents, together with a new algorithm for drawing them. Running Open image in new window on the documents then results in documents in the svg format with visually pleasing embedded animations. Our algorithm produces animations that satisfy a set of natural aesthetic criteria when possible. On the negative side, we show that one cannot always satisfy all criteria simultaneously and that minimizing their violations is NP-complete.
- Benito Van der Zander, Maciej Liskiewicz:
On Searching for Generalized Instrumental Variables.
In Proceedings of the The 19th International Conference on Artificial Intelligence and Statistics (AISTATS'16), pp. 1214-1222.
JMLR Proceedings,
2016.
Go to website - Benito van der Zander, Maciej Liskiewicz:
Separators and Adjustment Sets in Markov Equivalent DAGs.
In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI'16), Phoenix, Arizona USA, pp. 3315-3321.
AAAI Press,
2016.
Go to website
