- Max Bannach, Sebastian Berndt, Thorsten Ehlers:
Jdrasil: A Modular Library for Computing Tree Decompositions.
In International Symposium on Experimental Algorithms (SEA 2017), Volume 75 of LIPIcs, pp. 28:1--28:21.
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik,
2017.
Go to website | Show PDF | Show abstract
While the theoretical aspects concerning the computation of tree
width - one of the most important graph parameters - are well
understood, it is not clear how it can be computed
practically.We present the open source Java library
Jdrasil that implements several different state of the art
algorithms for this task. By experimentally comparing these
algorithms, we show that the default choices made in Jdrasil
lead to an competitive implementation (it took the third place in the
first PACE challenge) while also being easy to use and easy to extend.
- Sebastian Berndt, Maciej Liskiewicz:
Algorithm Substitution Attacks from a Steganographic Perspective.
In Proc. 24th ACM Conference on Computer and Communications Security (CCS 2017), pp. 1649-1660.
ACM Press,
2017.
Go to website | Show abstract
The goal of an algorithm-substitution attack (ASA), also called a
subversion attack (SA), is to replace an honest implementation of a
cryptographic tool by a subverted one which allows to leak private
information while generating output indistinguishable from the honest
output. Bellare, Paterson, and Rogaway provided at CRYPTO '14 a
formal security model to capture this kind of attacks and constructed
practically implementable ASAs against a large class of symmetric
encryption schemes. At CCS'15 Ateniese, Magri, and Venturi extended
the model to allow the attackers to work in a fully-adaptive and
continuous fashion and proposed subversion attacks against
digital signature schemes. Both papers also showed
impossibility of ASAs in cases when the cryptographic tools are
deterministic. Also at CCS'15, Bellare, Jaeger and Kane strengthened
the original model and proposed a universal ASA against sufficiently
random encryption schemes. In this paper we analyze ASAs from the
point of view of steganography - the well known concept of hiding the
presence of secret messages in legal communications. While a close
connection between ASAs and steganography is known, this lacks a
rigorous treatment. We consider the common computational model for
secret-key steganography and prove that successful ASAs correspond to
secure stegosystems on certain channels and vice versa. This formal
proof allows us to conclude that ASAs are stegosystems and to
»rediscover« several results concerning ASAs known in the steganographic
literature.
- Sebastian Berndt, Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
Learning Residual Alternating Automata.
Proc. 31st AAAI Conference on Artificial Intelligence (AAAI 2017), pp. 1749-1755.
AAAI Press,
2017.
Go to website | Show abstract
Residuality plays an essential role for learning finite automata.
While residual deterministic and non-deterministic
automata have been understood quite well, fundamental questions
concerning alternating automata (AFA) remain open.
Recently, Angluin, Eisenstat, and Fisman (2015) have initiated
a systematic study of residual AFAs and proposed an
algorithm called AL* – an extension of the popular L* algorithm
– to learn AFAs. Based on computer experiments
they have conjectured that AL* produces residual AFAs, but
have not been able to give a proof. In this paper we disprove
this conjecture by constructing a counterexample. As
our main positive result we design an efficient learning algorithm,
named AL**, and give a proof that it outputs residual
AFAs only. In addition, we investigate the succinctness of
these different FA types in more detail.
- Martin R. Schuster, Maciej Liskiewicz:
New Abilities and Limitations of Spectral Graph Bisection.
In 25th Annual European Symposium on Algorithms, (ESA) 2017, LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik,
2017.
- Till Tantau:
Applications of Algorithmic Metatheorems to Space Complexity and Parallelism (Invited Talk)..
In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), pp. 4:1--4:4.
DROPS,
2017.
Go to website | Show abstract
Algorithmic metatheorems state that if a problem can be described in a certain logic and the inputs are structured in a certain way, then the problem can be solved with a certain amount of resources. As an example, by Courcelle's Theorem all monadic second-order ("in a certain logic") properties of graphs of bounded tree width ("structured in a certain way") can be solved in linear time ("with a certain amount of resources"). Such theorems have become a valuable tool in algorithmics: If a problem happens to have the right structure and can be described in the right logic, they immediately yield a (typically tight) upper bound on the time complexity of the problem. Perhaps even more importantly, several complex algorithms rely on algorithmic metatheorems internally to solve subproblems, which considerably broadens the range of applications of these theorems. The talk is intended as a gentle introduction to the ideas behind algorithmic metatheorems, especially behind some recent results concerning space classes and parallel computation, and tries to give a flavor of the range of