- Maciej Liskiewicz, Krzysztof Lorys, Marek Piotrow:
On reversal bounded alternating Turing machines.
Theoretical Computer Science, 54(2-3):331-339, 1987.
Go to website - Maciej Liskiewicz, Krzysztof Lorys:
Alternating real-time computations.
Information Processing Letters, 28(6):311-316, 1988.
Go to website - Miroslaw Kutylowski, Maciej Liskiewicz, Krzysztof Lorys:
Reversal complexity classes for alternating Turing machines.
SIAM Journal on Computing, 19(2):207-221, 1990.
Go to website - Maciej Liskiewicz, Krzysztof Lorys:
Fast simulations of time-bounded one-tape Turing machines by space-bounded ones.
SIAM Journal on Computing, 19(3):511-521, 1990.
Go to website - Maciej Liskiewicz:
On the relationship between deterministic time and deterministic reversal.
Information Processing Letters, 45(3):143-146, 1993.
Go to website - Maciej Liskiewicz:
On the power of 1-tape off-line ATMs running in a bounded number of reversals.
Mathematical Systems Theory, 28:329-339, 1995.
Go to website - Maciej Liskiewicz, Rüdiger Reischuk:
The Sublogarithmic Alternating Space World.
SIAM Journal on Computing, 4(25):828-861, 1996.
Go to website - Maciej Liskiewicz, Rüdiger Reischuk:
On Small Space Complexity Classes of Stochastic Turing Machines and Arthur-Merlin-Games.
Computational Complexity, 3(8):273-307, 1999.
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 - 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 - 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 - 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 - 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 - 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 - 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 - Sebastian Berndt, Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
Learning residual alternating automata.
Information and Computation, (289):104981, 2022.
Go to website - 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 - 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 - 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, 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 - 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.
- 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 - 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 - 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.
- 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 - Maciej Liskiewicz, Rüdiger Reischuk, Ulrich Wölfel:
Grey-box steganography.
Theoretical Computer Science, (505):27-41, 2013.
Go to website - 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 - 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 - 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
