Maciej Liśkiewicz

AAAI Conference 2024 Conference Paper

Linear-Time Algorithms for Front-Door Adjustment in Causal Graphs

• Marcel Wienöbst
• Benito van der Zander
• Maciej Liśkiewicz

Causal effect estimation from observational data is a fundamental task in empirical sciences. It becomes particularly challenging when unobserved confounders are involved in a system. This paper focuses on front-door adjustment – a classic technique which, using observed mediators allows to identify causal effects even in the presence of unobserved confounding. While the statistical properties of the front-door estimation are quite well understood, its algorithmic aspects remained unexplored for a long time. In 2022, Jeong, Tian, and Bareinboim presented the first polynomial-time algorithm for finding sets satisfying the front-door criterion in a given directed acyclic graph (DAG), with an O(n³(n+m)) run time, where n denotes the number of variables and m the number of edges of the causal graph. In our work, we give the first linear-time, i.e., O(n+m), algorithm for this task, which thus reaches the asymptotically optimal time complexity. This result implies an O(n(n+m)) delay enumeration algorithm of all front-door adjustment sets, again improving previous work by a factor of n³. Moreover, we provide the first linear-time algorithm for finding a minimal front-door adjustment set. We offer implementations of our algorithms in multiple programming languages to facilitate practical usage and empirically validate their feasibility, even for large graphs.

NeurIPS Conference 2024 Conference Paper

On the Complexity of Identification in Linear Structural Causal Models

• Julian Dörfler
• Benito van der Zander
• Markus Bläser
• Maciej Liśkiewicz

Learning the unknown causal parameters of a linear structural causal model is a fundamental task in causal analysis. The task, known as the problem of identification, asks to estimate the parameters of the model from acombination of assumptions on the graphical structure of the model and observational data, represented as a non-causal covariance matrix. In this paper, we give a new sound and complete algorithm for generic identification which runs in polynomial space. By a standard simulation result, namely $\mathsf{PSPACE} \subseteq \mathsf{EXP}$, this algorithm has exponential running time which vastly improves the state-of-the-art double exponential time method using a Gröbner basis approach. The paper also presents evidence that parameter identification is computationally hard in general. In particular, we prove, that the taskasking whether, for a given feasible correlation matrix, there are exactly one or two or more parameter sets explaining the observed matrix, is hard for $\forall \mathbb{R}$, the co-class of the existential theory of the reals. In particular, this problem is $\mathsf{coNP}$-hard. To our best knowledge, this is the first hardness result for some notion of identifiability.

AIJ Journal 2023 Journal Article

Corrigendum to “Separators and adjustment sets in causal graphs: Complete criteria and an algorithmic framework” [Artif. Intell. 270 (2019) 1–40]

• Benito van der Zander
• Maciej Liśkiewicz
• Johannes Textor

JMLR Journal 2023 Journal Article

Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications

• Marcel Wienöbst
• Max Bannach
• Maciej Liśkiewicz

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. As we show in experiments, these breakthroughs make thought-to-be-infeasible strategies in active learning of causal structures and causal effect identification with regard to a Markov equivalence class practically applicable. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2023. ( edit, beta )

IJCAI Conference 2023 Conference Paper

The Hardness of Reasoning about Probabilities and Causality

• Benito van der Zander
• Markus Bläser
• Maciej Liśkiewicz

We study formal languages which are capable of fully expressing quantitative probabilistic reasoning and do-calculus reasoning for causal effects, from a computational complexity perspective. We focus on satisfiability problems whose instance formulas allow expressing many tasks in probabilistic and causal inference. The main contribution of this work is establishing the exact computational complexity of these satisfiability problems. We introduce a new natural complexity class, named succ∃R, which can be viewed as a succinct variant of the well-studied class ∃R, and show that these problems are complete for succ∃R. Our results imply even stronger limitations on the use of algorithmic methods for reasoning about probabilities and causality than previous state-of-the-art results that rely only on the NP- or ∃R-completeness of the satisfiability problems for some restricted languages.

I&C Journal 2022 Journal Article

Learning residual alternating automata

• Sebastian Berndt
• Maciej Liśkiewicz
• Matthias Lutter
• Rüdiger Reischuk

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 (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 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 finite automata (FA) types in more detail.

I&C Journal 2020 Journal Article

On the universal steganography of optimal rate

• Sebastian Berndt
• Maciej Liśkiewicz

In this work, we present the first secure stegosystem in the common computational model which, for any communication channel, is provably secure, reliable, and has nearly optimal bandwidth, but needs super-polynomial time. This solves several open problems about secret-key steganography in the computational model. In particular, our result answers affirmatively the question whether there exists a secure and reliable universal system of rate asymptotically larger than log ⁡ κ, where κ is the security parameter. Next, we prove a lower bound on the query complexity of stegosystems showing that our construction is optimal. This lower bound extends the results by Hopper et al. (2009) [19] and by Dedić et al. (2009) [22]. We also discuss universal steganography of optimal rate in the information-theoretic setting. We prove that an exponential number of samples is needed to embed messages in documents of high min-entropy. Our results, together with the result by Cachin (2004) [16], show that the situation of universal steganography in the computational and in the information-theoretic model is analogous: optimal universal steganography exists, but the protocols need super-polynomial time.

I&C Journal 2020 Journal Article

The generic combinatorial algorithm for image matching with classes of projective transformations

• Christian Rosenke
• Maciej Liśkiewicz

Image matching is an important task arising in video compression, optical character recognition, medical imaging, watermarking and in many others fields. Given two digital images A and B, image matching determines a transformation f for A such that it most closely resembles B. In this paper, we introduce the first general discretization technique that works for the class of projective transformations as well as plenty of its subclasses such as affine transformations and several combinations of scaling, rotation and translation. Based on this, we provide a fully generic image matching algorithm for all these classes that runs in polynomial time.

AIJ Journal 2019 Journal Article

Separators and adjustment sets in causal graphs: Complete criteria and an algorithmic framework

• Benito van der Zander
• Maciej Liśkiewicz
• Johannes Textor

Principled reasoning about the identifiability of causal effects from non-experimental data is an important application of graphical causal models. This paper focuses on effects that are identifiable by covariate adjustment, a commonly used estimation approach. We present an algorithmic framework for efficiently testing, constructing, and enumerating m-separators in ancestral graphs (AGs), a class of graphical causal models that can represent uncertainty about the presence of latent confounders. Furthermore, we prove a reduction from causal effect identification by covariate adjustment to m-separation in a subgraph for directed acyclic graphs (DAGs) and maximal ancestral graphs (MAGs). Jointly, these results yield constructive criteria that characterize all adjustment sets as well as all minimal and minimum adjustment sets for identification of a desired causal effect with multiple exposures and outcomes in the presence of latent confounding. Our results extend several existing solutions for special cases of these problems. Our efficient algorithms allowed us to empirically quantify the identifiability gap between covariate adjustment and the do-calculus in random DAGs and MAGs, covering a wide range of scenarios. Implementations of our algorithms are provided in the R package dagitty.

TCS Journal 2017 Journal Article

Security levels in steganography – Insecurity does not imply detectability

• Maciej Liśkiewicz
• Rüdiger Reischuk
• Ulrich Wölfel

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. However, stegosystems that fulfil the security notion used so far are quite inefficient. The current 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 insecurity considered so far. However, it is totally unclear how they could be successfully attacked when used in practice. This indicates that a different notion of security is needed which we call detectability. We propose different variants of (un)-detectability and discuss their appropriateness by constructing concrete examples of stegosystems and covertext distributions. As main technical contribution we design a framework for steganography that exploits the difficulty to get detailed information about 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.

TCS Journal 2013 Journal Article

Grey-box steganography

• Maciej Liśkiewicz
• Rüdiger Reischuk
• Ulrich Wölfel

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 investigations, the knowledge about the covertext channel was highly unbalanced: while the adversary was granted full knowledge, the encoder could only query a black-box sampling oracle. In such a situation, the only general steganographic technique known is rejection sampling. But this method requires exponential sampling complexity with respect to the number of message bits per covertext document. The other extreme, a white-box setting, where the encoder knows the covertext distribution perfectly, resp. the distribution is efficiently computable, is also unrealistic in practice. To resolve these deficiencies and to get a finer-grained security analysis, 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. We illustrate our concept with three examples of concept classes of different complexity: channels that can be described by monomials, by decision trees and by DNF-formulae. Their learning complexity ranges from easily learnable up to (probably) difficult to learn. A generic construction is given showing that besides the learning complexity, the efficiency of grey-box steganography depends on the complexity of the membership test, and suitable modification procedures. For the concept classes considered we present efficient algorithms for changing a covertext into a stegotext.

TCS Journal 2009 Journal Article

A combinatorial geometrical approach to two-dimensional robust pattern matching with scaling and rotation

• Christian Hundt
• Maciej Liśkiewicz
• Ragnar Nevries

The problem of two-dimensional pattern matching invariant under a given class of admissible transformations F is to find matches of transformed versions f ( P ) of a pattern P in a given text T, for all f in F. In this paper, pattern matching invariant under compositions of real valued scaling and rotation are investigated. We give a new discretization technique for this class of transformations and prove sharp lower and upper bounds on the number of different possibilities to transform a pattern in this way. Subsequently, we present the first efficient pattern matching algorithm invariant under compositions of scaling and rotation. The algorithm works in time O ( m 2 n 6 ) for patterns of size m 2 and texts of size n 2. We conclude with an experimental section to support the practical use of our results.

TCS Journal 2009 Journal Article

Improving the average delay of sorting

• Andreas Jakoby
• Maciej Liśkiewicz
• Rüdiger Reischuk
• Christian Schindelhauer

In previous work we have introduced an average case measure for the time complexity of Boolean circuits. Instead of fixed circuit depth, for each input we take the minimal number of time steps necessary to perform the computation for that particular input using gates that forward their output values as soon as possible. This measure is called delay. Based on it, the complexity of a whole class of functions that can be described as prefix computations has been analysed in detail. Here we consider the problem to sort large integers that are given in binary notation. Contrary to a word comparator sorting circuit C where a basic computational element, a comparator, is charged with a single time step to compare two elements, in a bit comparator circuit C ′ a comparison of two binary numbers has to be implemented by a Boolean subcircuit CM called comparator module that is built from Boolean gates of bounded fanin. Thus, compared to C, the depth of C ′ will be larger by a factor up to the depth of CM. Our goal is to minimize the average delay of bit comparator sorting circuits. The worst-case delay can be estimated by the depth of the circuit. For this worst-case measure two topologically quite different designs seem to be appropriate for the comparator modules: a tree-like one if the inputs are long numbers, otherwise a linear array working in a pipelined fashion. Inserting these into a word comparator circuit we get bit level sorting circuits for binary numbers of length m, for which the depth is either increased by a multiplicative factor of order log m or by an additive term of order m. We show that these obvious solutions can be improved significantly by constructing efficient sorting and merging circuits for the bit model that only suffer a constant factor time loss on the average if the inputs are uniformly distributed. This is done by designing suitable hybrid architectures of tree compaction and pipelining. These results can also be extended to classes of nonuniform distributions if we put a bound on the complexity of the distributions themselves.

TCS Journal 2003 Journal Article

The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes

• Maciej Liśkiewicz
• Mitsunori Ogihara
• Seinosuke Toda

Valiant (SIAM J. Comput. 8 (1979) 410–421) showed that the problem of computing the number of simple s–t paths in graphs is #P-complete both in the case of directed graphs and in the case of undirected graphs. Welsh (Complexity: Knots, Colourings and Counting, Cambridge University Press, Cambridge, 1993, p. 17) asked whether the problem of computing the number of self-avoiding walks of a given length in the complete two-dimensional grid is complete for #P1, the tally-version of #P. This paper offers a partial answer to the question of Welsh: it is #P-complete to compute the number of self-avoiding walks of a given length in a subgraph of a two-dimensional grid. Several variations of the problem are also studied and shown to be #P-complete. This paper also studies the problem of computing the number of self-avoiding walks in a subgraph of a hypercube. Similar completeness results are shown for the problem. By scaling the computation time to exponential, it is shown that computing the number of self-avoiding walks in hypercubes is a complete problem for #EXP in the case when a subgraph of a hypercube is specified by its dimension and a boolean circuit that accepts the nodes. Finally, this paper studies the complexity of testing whether a given word over the four-letter alphabet {U, D, L, R} represents a self-avoiding walk in a two-dimensional grid. A linear-space lower bound is shown for nondeterministic Turing machines with a 1-way input head to make this test.

TCS Journal 1987 Journal Article

On reversal bounded alternating Turing machines

• Maciej Liśkiewicz
• Krzysztof Loryś
• Marek Piotrów

It is known that, for one-tape nondeterministic Turing machines, S(n)-space and S(n)-reversal bounded machines (S(n) ⩾ n) recognize the same class of languages. We present a simulation of S(n)-space bounded alternating Turing machines (ATM) by one-tape lg∗ S(n)-reversal bounded ATMs. We also show that ATMs making a constant number of reversals recognize only regular languages. This shows that there is a striking difference in computational power between machines making a constant number of reversals and those making an ‘almost’ constant (i. e. , lg∗ n) number of reversals.