- Maciej Liskiewicz, Krzysztof Lorys, Marek Piotrow:
On reversal bounded alternating Turing machines.
Theoretical Computer Science, 54(2-3):331-339, 1987.
Website anzeigen - Maciej Liskiewicz, Krzysztof Lorys:
Alternating real-time computations.
Information Processing Letters, 28(6):311-316, 1988.
Website anzeigen - Miroslaw Kutylowski, Maciej Liskiewicz, Krzysztof Lorys:
Reversal complexity classes for alternating Turing machines.
SIAM Journal on Computing, 19(2):207-221, 1990.
Website anzeigen - 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.
Website anzeigen - Maciej Liskiewicz:
On the relationship between deterministic time and deterministic reversal.
Information Processing Letters, 45(3):143-146, 1993.
Website anzeigen - 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.
Website anzeigen - Maciej Liskiewicz, Rüdiger Reischuk:
The Sublogarithmic Alternating Space World.
SIAM Journal on Computing, 4(25):828-861, 1996.
Website anzeigen - 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.
Website anzeigen - 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.
Website anzeigen - Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
Approximating Schedules for Dynamic Graphs Efficiently.
Journal of Discrete Algorithms, 4(2):471-500, 2004.
Website anzeigen - Maciej Liskiewicz, Bodo Manthey:
New lower and upper bounds for the competitive ratio of transmission protocols.
Information Processing Letters, 89(6):297-301, 2004.
Website anzeigen - Jan Arpe, Andreas Jakoby, Maciej Liskiewicz:
One-Way Communication Complexity of Symmetric Boolean Functions.
RAIRO - Theoretical Informatics and Applications, 39(4):687-706, 2005.
Website anzeigen - 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.
Website anzeigen - Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
Space Efficient Algorithms for Directed Series-Parallel Graphs.
Journal of Algorithms, 2(60):85-114, 2006.
Website anzeigen - Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk, Christian Schindelhauer:
Improving the Average Delay of Sorting.
Theoretical Computer Science, 410(11):1030-1041, 2009.
Website anzeigen - 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.
Website anzeigen - Sebastian Berndt, Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
Learning residual alternating automata.
Information and Computation, (289):104981, 2022.
Website anzeigen - 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.
Website anzeigen - Sebastian Berndt, Maciej Liskiewicz:
On the universal steganography of optimal rate.
Information and Computation, 104632(Available online 14 October 2020)2020.
Website anzeigen - 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.
Website anzeigen - 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.
Website anzeigen | Zusammenfassung anzeigen
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.
Website anzeigen - Sebastian Berndt, Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
Learning Residual Alternating Automata.
Electronic Colloquium on Computational Complexity (ECCC), 24(46)2017.
Website anzeigen | Zusammenfassung anzeigen
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.
Website anzeigen | Zusammenfassung anzeigen
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.
Website anzeigen - 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.
Website anzeigen - 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.
Website anzeigen | Zusammenfassung anzeigen
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.
Website anzeigen - Maciej Liskiewicz, Rüdiger Reischuk, Ulrich Wölfel:
Grey-box steganography.
Theoretical Computer Science, (505):27-41, 2013.
Website anzeigen - Maciej Liskiewicz, Martin R. Schuster:
Improved Analysis of an Exact Algorithm for Cubic Graph TSP.
CoRR, (abs/1207.4694)2012.
Website anzeigen - Johannes Textor, Maciej Liskiewicz:
Adjustment Criteria in Causal Diagrams: An Algorithmic Perspective.
CoRR, (abs/1202.3764)2012.
Website anzeigen - Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey:
Privacy in Non-private Environments.
Theory of Computing Systems, 48(1):211-245, 2011.
Website anzeigen - Christian Hundt, Maciej Liskiewicz:
New complexity bounds for image matching under rotation and scaling.
Journal of Discrete Algorithms, 9:122–136, 2011.
Website anzeigen - Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey:
Privacy in Non-Private Environments.
Theory of Computing Systems, 2009.
Website anzeigen - 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.
Website anzeigen
