2024

• Marcel Wienöbst, Benito van der Zander, Maciej Liskiewicz:
  Linear-Time Algorithms for Front-Door Adjustment in Causal Graphs.
  In AAAI Conference on Artificial Intelligence (AAAI 2024), pp. 20577-20584. , 2024.
  Go to website

2023

• Malte Luttermann, Marcel Wienöbst, Maciej Liskiewicz:
  Practical Algorithms for Orientations of Partially Directed Graphical Models.
  In Conference on Causal Learning and Reasoning (CLeaR 2023), pp. 1-20. PLRM, 2023.
  Go to website
• Thore Tiemann, Sebastian Berndt, Thomas Eisenbarth, Maciej Liskiewicz:
  "Act natural!": Having a Private Chat on a Public Blockchain.
  In 8th IEEE European Symposium on Security and Privacy (EuroS&P '23), IEEE, 2023.
• Marcel Wienöbst, Malte Luttermann, Max Bannach, Maciej Liskiewicz:
  Efficient enumeration of Markov equivalent DAGs.
  In AAAI Conference on Artificial Intelligence (AAAI 2023), pp. 12313-12320. , 2023.
  Go to website
• Marcel Wienöbst, Max Bannach, Maciej Liskiewicz:
  Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications.
  Journal of Machine Learning Research, (24.213):1-45, 2023.
  Go to website
• Benito van der Zander, Markus Bläser, Maciej Liskiewicz:
  The hardness of reasoning about probabilities and causality.
  In International Joint Conference on Artificial Intelligence (IJCAI 2023), pp. 5730. , 2023.
  Show PDF

2022

• Sebastian Berndt, Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
  Learning residual alternating automata.
  Information and Computation, (289):104981, 2022.
  Go to website
• Marcel Wienöbst, Max Bannach, Maciej Liskiewicz:
  A New Constructive Criterion for Markov Equivalence of MAGs.
  In Proc. of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence (UAI 2022), pp. 2107-2116. PMLR, 2022.
  Go to website
• Benito van der Zander, Marcel Wienöbst, Markus Bläser, Maciej Liskiewicz:
  Identification in Tree-shaped Linear Structural Causal Models.
  In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, pp. 6770-6792. PLMR, 2022.
  Go to website

2021

• Okan Seker, Thomas Eisenbarth, Maciej Liskiewicz:
  A White-Box Masking Scheme Resisting Computational and Algebraic Attacks.
  IACR Transactions on Cryptographic Hardware and Embedded Systems, 2(2021):61–105, 2021.
  Go to website
• Marcel Wienöbst, Maciej Liskiewicz:
  An Approach to Reduce the Number of Conditional Independence Tests in the PC Algorithm.
  In Proceeding of 44th German Conference on AI (KI 2021), Volume 12873 of Lecture Notes in Computer Science, pp. 276-288. Springer, 2021.
  Go to website
• Marcel Wienöbst, Max Bannach, Maciej Liskiewicz:
  Extendability of Causal Graphical Models: Algorithms and Computational Complexity.
  In Proc. of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence (UAI 2021), pp. 1248-1257. PMLR, 2021.
  Go to website
• Marcel Wienöbst, Max Bannach, Maciej Liskiewicz:
  Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs.
  In Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI'21), pp. 12198-12206. AAAI Press, 2021.
  Go to website | Show PDF | Show abstract
  
  Counting and sampling directed acyclic graphs from a Markov equivalence class are fundamental tasks in graphical causal analysis. In this paper, we show that these tasks can be performed in polynomial time, solving a long-standing open problem in this area. Our algorithms are effective and easily implementable. Experimental results show that the algorithms significantly outperform state-of-the-art methods.
• Marcel Wienöbst, Max Bannach, Maciej Liskiewicz:
  Recent Advances in Counting and Sampling Markov Equivalent DAGs.
  In Proceeding of 44th German Conference on AI (KI 2021), Volume 12873 of Lecture Notes in Computer Science, pp. 271-275. Springer, 2021.
  Go to website | Show abstract
  
  Counting and sampling directed acyclic graphs (DAGs) from a Markov equivalence class are fundamental tasks in graphical causal analysis. In this paper, we discuss recently proposed polynomial-time algorithms for these tasks. The presented result solves a long-standing open problem in graphical modelling. Experiments show that the proposed algorithms are implementable and effective in practice. Our paper is an extended abstract of the work [24], honored as an AAAI-21 Distinguished Paper at the 35th AAAI Conference on Artificial Intelligence.

2020

• Sebastian Berndt, Maciej Liskiewicz:
  On the universal steganography of optimal rate.
  Information and Computation, 104632(Available online 14 October 2020)2020.
  Go to website
• Christian Rosenke, Maciej Liskiewicz:
  The generic combinatorial algorithm for image matching with classes of projective transformations.
  Information and Computation, 104550(Available online 25 March 2020)2020.
  Go to website
• Okan Seker, Thomas Eisenbarth, Maciej Liskiewicz:
  A White-Box Masking Scheme Resisting Computational and Algebraic Attacks.
  Technical report 2020 (2020): 443., IACR Cryptol. ePrint Arch., 2020.
  Go to website
• Marcel Wienöbst, Maciej Liskiewicz:
  Recovering Causal Structures from Low-Order Conditional Independencies.
  In Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI'20), New York, New York USA, pp. 10302-10309. AAAI Press, 2020.
  Go to website | Show PDF | Show abstract
  
  One of the common obstacles for learning causal models from data is that high-order conditional independence (CI) relationships between random variables are difficult to estimate. Since CI tests with conditioning sets of low order can be performed accurately even for a small number of observations, a reasonable approach to determine casual structures is to base merely on the low-order CIs. Recent research has confirmed that, e.g. in the case of sparse true causal models, structures learned even from zero- and first-order conditional independencies yield good approximations of the models. However, a challenging task here is to provide methods that faithfully explain a given set of low-order CIs. In this paper we propose an algorithm which, for a given set of conditional independencies of order less or equal to $k$, where $k$ is a small fixed number, computes a faithful graphical representation of the given set. Our results complete and generalize the previous work on learning from pairwise marginal independencies. Moreover, they enable to improve upon the 0-1 graph model which, e.g. is heavily used in the estimation of genome networks.

2019

• Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
  Proper learning of k-term DNF formulas from satisfying assignments.
  Journal of Computer and System Sciences, 106:129-144, 2019.
  Go to website | Show abstract
  
  In certain applications there may be only positive examples available to learn concepts of a class of interest. Furthermore, learning has to be done properly, i.e. the hypothesis space has to coincide with the concept class, and without false positives, i.e. the hypothesis always has to be a subset of the real concept (one-sided error). For the well studied class of k-term DNF formulas it has been known that learning is difficult. Unless RP=NP, it is not feasible to learn k-term DNF formulas properly in a distribution-free sense even if both positive and negative examples are available and even if false positives are allowed. This paper constructs an efficient algorithm that, for fixed but arbitrary k and q, if examples are drawn from q-bounded distributions, it properly learns the class of k-term DNFs without false positives from positive examples alone with arbitrarily small relative error.
• Benito van der Zander, Maciej Liskiewicz:
  Finding minimal d-separators in linear time and applications.
  In Proceedings of the 35th Conference on Uncertainty in Artificial Intelligence (UAI'19), AUAI Press, 2019.
  Show PDF
• Benito van der Zander, Maciej Liskiewicz, Johannes Textor:
  Separators and adjustment sets in causal graphs: Complete criteria and an algorithmic framework.
  Artificial Intelligence, Vol. 270, Pages 1-40, (270):1-40, 2019.
  Go to website

2018

• Sebastian Berndt, Maciej Liskiewicz:
  On the Gold Standard for Security of Universal Steganography.
  In Proc. Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Volume vol. 10820 of LNCS, pp. 29-60. Springer, 2018.
  Go to website | Show abstract
  
  While symmetric-key steganography is quite well understood both in the information-theoretic and in the computational setting, many fundamental questions about its public-key counterpart resist persistent attempts to solve them. The computational model for public-key steganography was proposed by von Ahn and Hopper in EUROCRYPT 2004. At TCC 2005, Backes and Cachin gave the first universal public-key stegosystem - i.e. one that works on all channels - achieving security against replayable chosen-covertext attacks (SS-RCCA) and asked whether security against non-replayable chosen-covertext attacks (SS-CCA) is achievable. Later, Hopper (ICALP 2005) provided such a stegosystem for every efficiently sampleable channel, but did not achieve universality. He posed the question whether universality and SS-CCA-security can be achieved simultaneously. No progress on this question has been achieved since more than a decade. In our work we solve Hopper's problem in a somehow complete manner: As our main positive result we design an SS-CCA-secure stegosystem that works for every memoryless channel. On the other hand, we prove that this result is the best possible in the context of universal steganography. We provide a family of 0-memoryless channels - where the already sent documents have only marginal influence on the current distribution - and prove that no SS-CCA-secure steganography for this family exists in the standard non-look-ahead model.
• Sebastian Berndt, Maciej Liskiewicz:
  On the Gold Standard for Security of Universal Steganography.
  Technical report 106, IACR Cryptology ePrint Archive, 2018.
  Go to website
• Benito van der Zander, Maciej Liskiewicz, Johannes Textor:
  Separators and adjustment sets in causal graphs: Complete criteria and an algorithmic framework.
  Technical report arXiv:1803.00116 (2018), arXiv preprint, 2018.
  Show PDF

2017

• 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.
  Electronic Colloquium on Computational Complexity (ECCC), 24(46)2017.
  Go to website | Show abstract
  
  Residuality plays an essential role for learning finite automata. While residual deterministic and nondeterministic automata have been understood quite well, fundamental questions concerning alternating automata (AFA) remain open. Recently, Angluin, Eisenstat, and Fisman 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 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.
• 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.
• Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
  Proper Learning of k-term DNF Formulas from Satisfying Assignments.
  Electronic Colloquium on Computational Complexity (ECCC), 24(114)2017.
  Go to website | Show abstract
  
  In certain applications there may only be positive samples available to to learn concepts of a class of interest, and this has to be done properly, i.e. the hypothesis space has to coincide with the concept class, and without false positives, i.e. the hypothesis always has be a subset of the real concept (one-sided error). For the well studied class of k-term DNF formulas it has been known that learning is difficult. Unless RP = NP, it is not feasible to learn k-term DNF formulas properly in a distribution-free sense even if both positive and negative samples are available and even if false positives are allowed. This paper constructs an efficient algorithm that for arbitrary fixed k, if samples are drawn from distributions like uniform or q-bounded ones, properly learns the class of k-term DNFs without false positives from positive samples alone with arbitrarily small relative error.
• Maciej Liskiewicz, Rüdiger Reischuk, Ulrich Wölfel:
  Security levels in steganography - Insecurity does not imply detectability.
  Theoret. Comput. Sci., (692):25-45, 2017.
  Go to website
• Martin R. Schuster, Maciej Liskiewicz:
  New Abilities and Limitations of Spectral Graph Bisection.
  Technical report 1701.01337, arXiv, 2017.
  Go to website | Show abstract
  
  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.
• 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.

2016

• 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.
• Johannes Textor, Benito van der Zander, Mark S. Gilthorpe, Maciej Liskiewicz, George T.H. Ellison:
  Robust causal inference using Directed Acyclic Graphs: the R package ’dagitty’.
  International Journal of Epidemiology, 6(45):1887-1894, 2016.
  Go to website
• 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

2015

• Matthias Ernst, Maciej Liskiewicz, Rüdiger Reischuk:
  Algorithmic Learning for Steganography: Proper Learning of k-term DNF Formulas from Positive Samples.
  In Proc. International Symposium on Algorithms and Computation (ISAAC 2015), Volume 9472 of Lecture Notes in Computer Science, pp. 151-162. Springer, 2015.
  Go to website | Show abstract
  
  Proper learning from positive samples is a basic ingredient for designing secure steganographic systems for unknown covertext channels. In addition, security requirements imply that the hypothesis should not contain false positives. We present such a learner for k-term DNF formulas for the uniform distribution and a generalization to q-bounded distributions. We briefly also describe how these results can be used to design a secure stegosystem.
• Maciej Liskiewicz, Rüdiger Reischuk, Ulrich Wölfel:
  Security Levels in Steganography - Insecurity does not Imply Detectability.
  Electronic Colloquium on Computational Complexity (ECCC), 22(10)2015.
  Go to website | Show abstract
  
  This paper takes a fresh look at security notions for steganography -- the art of encoding secret messages into unsuspicious covertexts such that an adversary cannot distinguish the resulting stegotexts from original covertexts. Stegosystems that fulfill the security notion used so far, however, are quite inefficient. This setting is not able to quantify the power of the adversary and thus leads to extremely high requirements. We will show that there exist stegosystems that are not secure with respect to the measure considered so far, still cannot be detected by the adversary in practice. This indicates that a different notion of security is needed which we call \emph{undetectability}. We propose different variants of (un)-detectability and discuss their appropriateness. By constructing concrete examples of stegosystems and covertext distributions it is shown that among these measures only one manages to clearly and correctly differentiate different levels of security when compared to an intuitive understanding in real life situations. We have termed this \emph{detectability on average}. As main technical contribution we design a framework for steganography that exploits the difficulty to learn the covertext distribution. This way, for the first time a tight analytical relationship between the task of discovering the use of stegosystems and the task of differentiating between possible covertext distributions is obtained.
• Johannes Textor, Alexander Idelberger, Maciej Liskiewicz:
  On the Faithful DAGs of a Dependency Graph.
  In Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence (UAI'15), pp. 882-891. AUAI Press, 2015.
  Show PDF
• Benito van der Zander, Johannes Textor, Maciej Liskiewicz:
  Efficiently Finding Conditional Instruments for Causal Inference.
  In IJCAI 2015, Proceedings of the 24th International Joint Conference on Artificial Intelligence, Buenos Aires, Argentina, July 25-31, 2015, pp. 3243-3249. AAAI Press / International Joint Conferences on Artificial Intelligence, 2015.
  Show PDF

2014

• Alexander Idelberger, Maciej Liskiewicz:
  On the Computational Complexity of Partitioning Weighted Points into a Grid of Quadrilaterals.
  In Proceedings of the 26th Canadian Conference on Computational Geometry (CCCG'14), Halifax, Nova Scotia, Canada, 2014.
  Go to website
• Maciej Liskiewicz, Martin R. Schuster:
  A new upper bound for the traveling salesman problem in cubic graphs.
  Journal of Discrete Algorithms, (27):1-20, 2014.
  Go to website
• Johannes Textor, Katharina Dannenberg, Maciej Liskiewicz:
  A Generic Finite Automata Based Approach to Implementing Lymphocyte Repertoire Models.
  In Proceedings of the Annual Conference on Genetic and Evolutionary Computation (GECCO'14), pp. 129-136. ACM Press, 2014.
  Go to website
• Benito van der Zander, Johannes Textor, Maciej Liskiewicz:
  Constructing Separators and Adjustment Sets in Ancestral Graphs.
  In Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence (UAI'14), Quebec, Canada, pp. 907-916. AUAI Press, 2014.
  Show PDF

2013

• Maciej Liskiewicz, Martin R. Schuster:
  A new upper bound for the traveling salesman problem in cubic graphs.
  In 12th Cologne-Twente Workshop on Graphs and Combinatorial, Optimization, Enschede, Netherlands, May 21-23, 2013, Volume WP 13-01 of CTIT Workshop Proceedings, pp. 159-162. , 2013.
• Maciej Liskiewicz, Rüdiger Reischuk, Ulrich Wölfel:
  Grey-box steganography.
  Theoretical Computer Science, (505):27-41, 2013.
  Go to website

2012

• Maciej Liskiewicz, Martin R. Schuster:
  Improved Analysis of an Exact Algorithm for Cubic Graph TSP.
  CoRR, (abs/1207.4694)2012.
  Go to website
• Johannes Textor, Maciej Liskiewicz:
  Adjustment Criteria in Causal Diagrams: An Algorithmic Perspective.
  CoRR, (abs/1202.3764)2012.
  Go to website

2011

• Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey:
  Privacy in Non-private Environments.
  Theory of Computing Systems, 48(1):211-245, 2011.
  Go to website
• Christian Hundt, Maciej Liskiewicz:
  New complexity bounds for image matching under rotation and scaling.
  Journal of Discrete Algorithms, 9:122–136, 2011.
  Go to website
• Maciej Liskiewicz, Rüdiger Reischuk, Ulrich Wölfel:
  Grey-Box Steganography.
  Volume 6648 of Lecture Notes in Computer Science, pp. 390-402. Springer Verlag, Heidelberg, in Proceedings 8. TAMC, 2011.
  Go to website
• Johannes Textor, Maciej Liskiewicz:
  Adjustment Criteria in Causal Diagrams: An Algorithmic Perspective.
  In Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence (UAI 2011), pp. 681-688. AUAI Press, 2011.
  Show PDF | Go to website

2010

• Maciej Liskiewicz, Johannes Textor:
  Negative Selection Algorithms Without Generating Detectors.
  In Proceedings of the 12th annual conference on Genetic and evolutionary computation (GECCO'10), pp. 1047-1054. ACM, 2010.
  Show PDF | Go to website | Show abstract
  
  Negative selection algorithms are immune-inspired classifiers that are trained on negative examples only. Classification is performed by generating detectors that match none of the negative examples, and these detectors are then matched against the elements to be classified. This can be a performance bottleneck: A large number of detectors may be required for acceptable sensitivity, or finding detectors that match none of the negative examples may be difficult. In this paper, we show how negative selection can be implemented without generating detectors explicitly, which for many detector types leads to polynomial time algorithms whereas the common approach to sample detectors randomly takes exponential time in the worst case. In particular, we show that negative selection on strings with generating all detectors can be efficiently simulated without detectors if, and only if, an associated decision problem can be answered efficiently, regardless the detector type. We also show how to efficiently simulate the more general case in which only a limited number of detectors is generated. For many detector types, this non-exhaustive negative selection is more meaningful but it can be computationally more difficult, which we illustrate using Boolean monomials.

2009

• Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk, Christian Schindelhauer:
  Improving the Average Delay of Sorting.
  Theoretical Computer Science, 410(11):1030-1041, 2009.
  Go to website
• Maciej Liskiewicz, Rüdiger Reischuk, Ulrich Wölfel:
  Grey-Box Steganography.
  Technical report SIIM-TR-A-09-03, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2009.
  Show PDF | Show abstract
  
  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.
• Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey:
  Privacy in Non-Private Environments.
  Theory of Computing Systems, 2009.
  Go to website
• Christian Hundt, Maciej Liskiewicz, Ragnar Nevries:
  A Combinatorial Geometric Approach to Two-dimensional Robustly Pattern Matching with Scaling and Rotation.
  Theoretical Computer Science, 51(410):5317-5333, 2009.
  Go to website
• Christian Hundt, Maciej Liskiewicz:
  New Complexity Bounds for Image Matching under Rotation and Scaling.
  In Proceedings of Symposium on Combinatorial Pattern Matching (CPM), Volume 5577 of Lecture Notes in Computer Science, pp. 127-141. Springer, 2009.
  Go to website

2008

• Christian Hundt, Maciej Liskiewicz:
  Combinatorial Bounds and Algorithmic Aspects of Image Matching under Projective Transformations.
  In Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science (MFCS), Volume 5162 of Lecture Notes in Computer Science, pp. 395-406. Springer, 2008.
  Go to website
• Christian Hundt, Maciej Liskiewicz:
  Two-dimensional Pattern Matching with Combined Scaling and Rotation.
  In Proceedings of the 19th Symposium on Combinatorial Pattern Matching (CPM), Volume 5029 of Lecture Notes in Computer Science, pp. 5-17. Springer, 2008.
  Go to website
• Andreas Jacoby, Maciej Liskiewicz, Aleksander Madry:
  Susceptible Two-party Quantum Computations.
  In in Proceedings of the 2nd International Conference on Information Theoretic Security (ICITS), Volume 5155 of Lecture Notes in Computer Science, pp. 121-136. Springer, 2008.
  Go to website
• Maciej Liskiewicz, Ulrich Wölfel:
  Computational Aspects of Digital Steganography.
  In Multimedia Forensics and Security, pp. 193-211. Information Science Reference, Hershey, New York, 2008.
  Go to website

2007

• Christian Hundt, Maciej Liskiewicz:
  On the Complexity of Affine Image Matching.
  In Proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS 2007), Volume 4393 of Lecture Notes in Computer Science, pp. 284-295. Springer, 2007.
  Go to website
• Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk, Christian Schindelhauer:
  Improving the Average Delay of Sorting.
  In 4th International Conference, Theory and Applications of Models of Computation, TAMC 2007, Volume 4484 of Lecture Notes in Computer Science, pp. 330-341. Springer, 2007.
  Go to website
• Maciej Liskiewicz, Rüdiger Reischuk, Guest Eds.:
  Theory of Computing Systems.
  Volume 41/2 of Theory of Computing Systems, Springer, 2007.
  Go to website

2006

• Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey:
  Private computation -- 2-connected versus 1-connected networks.
  Journal of Cryptology, 19(3):341-357, 2006.
  Go to website
• Christian Hundt, Maciej Liskiewicz, Ulrich Wölfel:
  Provably Secure Steganography and the Complexity of Sampling.
  In Algorithms and Computation, Volume 4288 of Lecture Notes in Computer Science, pp. 754-763. Springer, 2006.
  Go to website
• Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
  Space Efficient Algorithms for Directed Series-Parallel Graphs.
  Journal of Algorithms, 2(60):85-114, 2006.
  Go to website
• Maciej Liskiewicz:
  Multiparty Computations in Non-Private Environments.
  In Information Transfer and Combinatorics, Volume 4123 of Lecture Notes in Computer Science, pp. 1082-1084. Springer, 2006.
  Go to website

2005

• Jan Arpe, Andreas Jakoby, Maciej Liskiewicz:
  One-Way Communication Complexity of Symmetric Boolean Functions.
  RAIRO - Theoretical Informatics and Applications, 39(4):687-706, 2005.
  Go to website
• Andreas Jakoby, Maciej Liskiewicz:
  Revealing Additional Information in Two-Party Computations.
  In Proc. of the 11th Ann. Int. Conf. on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2005), Volume 3788 of Lecture Notes in Computer Science, pp. 121-135. Springer, 2005.
  Go to website
• Maciej Liskiewicz, Ulrich Wölfel:
  On the Intractability of Inverting Geometric Distortions in Watermarking Schemes.
  In Proc. 7th Information Hiding Workshop (IH 2005), Volume 3727 of Lecture Notes in Computer Science, pp. 176-188. Springer, 2005.
  Go to website
• Maciej Liskiewicz, Rüdiger Reischuk:
  Proceedings of the 15th International Symposium On Fundamentals of Computation Theory (FCT), Lübeck 2005.
  Volume 3623 of Lecture Notes in Computer Science, Springer, 2005.
  Go to website
• Maciej Liskiewicz, Rüdiger Reischuk:
  Proceedings of the 15th International Symposium On Fundamentals of Computation Theory (FCT), Lübeck 2005.
  Volume 3623 of Lecture Notes in Computer Science, Springer, 2005.

2004

• Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey:
  Privacy in Non-Private Environments.
  In Proc. 10th Ann. Int. Conf. on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2004), Volume 3329 of Lecture Notes in Computer Science, pp. 137-151. Springer, 2004.
  Go to website
• Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
  Approximating Schedules for Dynamic Graphs Efficiently.
  Journal of Discrete Algorithms, 4(2):471-500, 2004.
  Go to website
• Maciej Liskiewicz, Bodo Manthey:
  New lower and upper bounds for the competitive ratio of transmission protocols.
  Information Processing Letters, 89(6):297-301, 2004.
  Go to website
• Maciej Liskiewicz, Hemant J. Purohit, Dhananjay V. Raje:
  Relation of residues in the variable region of 16S rDNA sequences and their relevance to genus-specificity.
  In Proc. 4th Workshop on Algorithms in Bioinformatics (WABI 2004), Volume 3240 of Lecture Notes in Computer Science, pp. 362-373. Springer, 2004.
  Go to website

2003

• Jan Arpe, Andreas Jakoby, Maciej Liskiewicz:
  One-Way Communication Complexity of Symmetric Boolean Functions.
  In Proc. 14th International Symposium on Fundamentals of Computation Theory (FCT 2003), Volume 2751 of Lecture Notes in Computer Science, pp. 158-170. Springer, 2003.
  Go to website
• Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
  Private Computations in Networks: Topology versus Randomness.
  In 21 GI Symposium on Theoretical Aspects of Computer Science STACS'2003, Volume 2607 of Lecture Notes in Computer Science, pp. 189-198. Springer, 2003.
  Go to website
• Maciej Liskiewicz, Mitsunori Ogihara, Seinosuke Toda:
  Counting Self-avoiding Walks in Some Regular Graphs.
  SIGACT News, 34(3):26-39, 2003.
• Maciej Liskiewicz, Mitsunori Ogihara, Seinosuke Toda:
  The Complexity of Counting Self-avoiding Walks in Subgraphs of Two-dimensional Grids and Hypercubes.
  Theoretical Computer Science, 304(1-3):129-156, 2003.
  Go to website

2002

• Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Siebert:
  Private Computation - k-Connected versus 1-Connected Networks.
  In Proc. 22nd Annual International Association for Cryptologic Research (IACR) Crypto Conference (CRYPTO 2002),, Volume 2442 of Lecture Notes in Computer Science, pp. 194-209. Springer, 2002.
  Go to website
• Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
  Dynamic Process Graphs and the Complexity of Scheduling.
  Technical report SIIM-TR-A-00-02, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2002.
  Show postscript | Show abstract
  
  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.
• Andreas Jakoby, Maciej Liskiewicz:
  Paths Problems in Symmetric Logarithmic Space.
  In Proc. 29th International Colloquium on Automata, Languages, and Programming (ICALP 2002), Volume 2380 of Lecture Notes in Computer Science, pp. 269-280. Springer, 2002.
  Go to website

2001

• Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
  Space Efficient Algorithms for Series-Parallel Graphs.
  In 18 GI-MIMD Symposium on Theoretical Aspects of Computer Science STACS'2001, Volume 2010 of Lecture Notes in Computer Science, pp. 339-352. Springer, 2001.
  Go to website
• Andreas Jakoby, Maciej Liskiewicz:
  The Complexity of Some Basic Problems for Dynamic Process Graphs.
  In Proc. 12th Annual International Symposium on Algorithms and Computation (ISAAC 2001), Volume 2223 of Lecture Notes in Computer Science, pp. 562-574. Springer, 2001.
  Go to website

2000

• Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
  Space Efficient Algorithms for Series-Parallel Graphs.
  Technical report SIIM-TR-A-00-17, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2000.
  Show postscript | Show abstract
  
  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.
  In 26. Int. Workshop on Graph-Theoretical Concepts in Computer Science WG'2000, Volume 1928 of Lecture Notes in Computer Science, pp. 230-242. Springer, 2000.
  Go to website
• Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
  The Expressive Power and Complexity of Dynamic Process Graphs.
  Technical report SIIM-TR-A-00-07, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2000.
  Show postscript | Show abstract
  
  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.