- Krzysztof Lorys, Maciej Liskiewicz:
Two applications of Fürer's counter to one-tape nondeterministic TMs,
In Proc. Mathematical Foundations of Computer Science (MFCS 88), Band 324 von Lecture Notes in Computer Science, S. 445-453.
Springer,
1988.
Website anzeigen - Maciej Liskiewicz, Krzysztof Lorys:
On reversal complexity for alternating TMs.
In Proc. 30th Annual IEEE Symposium on the Foundations of Computer Science (FOCS 89), S. 618-623.
IEEE Computer Society Press,
1989.
Website anzeigen - Maciej Liskiewicz, Krzysztof Lorys:
Some time-space bounds for one-tape deterministic Turing machines.
In Proc. Fundamentals of Computations Theory (FCT 89), Band 380 von Lecture Notes in Computer Science, S. 297-307.
Springer,
1989.
Website anzeigen - Maciej Liskiewicz, Rüdiger Reischuk:
Separating the Lower Levels of the Sublogarithmic Space Hierarchy.
In 10. GI-AFCET Symposium on Theoretical Aspects of Computer Science STACS'93, Band 665 von Lecture Notes in Computer Science, S. 16-27.
Springer,
1993.
Website anzeigen - Maciej Liskiewicz, Rüdiger Reischuk:
The Complexity World below Logarithmic Space.
In 9. Ann. IEEE - SIGACT - EATCS Symposium on Structure in Complexity Theory STRUCTURES'94, S. 64-78.
IEEE Computer Society,
1994.
- Maciej Liskiewicz, Rüdiger Reischuk:
Computational Limitations of Stochastic Turing Machines and Arthur-Merlin Games with Small Space Bounds.
In 22. Int. Symposium on Mathematical Foundations of Computer Science MFCS'97, Band 1295 von Lecture Notes in Computer Science, S. 91-107.
Springer,
1997.
Website anzeigen - Maciej Liskiewicz:
Interactive Proof Systems with Public Coin: Lower Space Bounds and Hierarchies of Complexity Classes.
In Proc. 14th Symposium on Theoretical Aspects of Computer Science (STACS 1997), Band 1200 von Lecture Notes in Computer Science, S. 129-140.
Springer,
1997.
Website anzeigen - Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
Scheduling Dynamic Graphs.
In 16. GI-MIMD Symposium on Theoretical Aspects of Computer Science STACS'99, Band 1563 von Lecture Notes in Computer Science, S. 383-393.
Springer,
1999.
Website anzeigen - 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, Band 1928 von Lecture Notes in Computer Science, S. 230-242.
Springer,
2000.
Website anzeigen - 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, Band 2010 von Lecture Notes in Computer Science, S. 339-352.
Springer,
2001.
Website anzeigen - 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), Band 2223 von Lecture Notes in Computer Science, S. 562-574.
Springer,
2001.
Website anzeigen - 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),, Band 2442 von Lecture Notes in Computer Science, S. 194-209.
Springer,
2002.
Website anzeigen - Andreas Jakoby, Maciej Liskiewicz:
Paths Problems in Symmetric Logarithmic Space.
In Proc. 29th International Colloquium on Automata, Languages, and Programming (ICALP 2002), Band 2380 von Lecture Notes in Computer Science, S. 269-280.
Springer,
2002.
Website anzeigen - 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), Band 2751 von Lecture Notes in Computer Science, S. 158-170.
Springer,
2003.
Website anzeigen - 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, Band 2607 von Lecture Notes in Computer Science, S. 189-198.
Springer,
2003.
Website anzeigen - 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), Band 3329 von Lecture Notes in Computer Science, S. 137-151.
Springer,
2004.
Website anzeigen - 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), Band 3240 von Lecture Notes in Computer Science, S. 362-373.
Springer,
2004.
Website anzeigen - 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), Band 3788 von Lecture Notes in Computer Science, S. 121-135.
Springer,
2005.
Website anzeigen - Maciej Liskiewicz, Ulrich Wölfel:
On the Intractability of Inverting Geometric Distortions in Watermarking Schemes.
In Proc. 7th Information Hiding Workshop (IH 2005), Band 3727 von Lecture Notes in Computer Science, S. 176-188.
Springer,
2005.
Website anzeigen - Christian Hundt, Maciej Liskiewicz, Ulrich Wölfel:
Provably Secure Steganography and the Complexity of Sampling.
In Algorithms and Computation, Band 4288 von Lecture Notes in Computer Science, S. 754-763.
Springer,
2006.
Website anzeigen - Maciej Liskiewicz:
Multiparty Computations in Non-Private Environments.
In Information Transfer and Combinatorics, Band 4123 von Lecture Notes in Computer Science, S. 1082-1084.
Springer,
2006.
Website anzeigen - 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), Band 4393 von Lecture Notes in Computer Science, S. 284-295.
Springer,
2007.
Website anzeigen - 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, Band 4484 von Lecture Notes in Computer Science, S. 330-341.
Springer,
2007.
Website anzeigen - 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), Band 5162 von Lecture Notes in Computer Science, S. 395-406.
Springer,
2008.
Website anzeigen - Christian Hundt, Maciej Liskiewicz:
Two-dimensional Pattern Matching with Combined Scaling and Rotation.
In Proceedings of the 19th Symposium on Combinatorial Pattern Matching (CPM), Band 5029 von Lecture Notes in Computer Science, S. 5-17.
Springer,
2008.
Website anzeigen - Andreas Jacoby, Maciej Liskiewicz, Aleksander Madry:
Susceptible Two-party Quantum Computations.
In in Proceedings of the 2nd International Conference on Information Theoretic Security (ICITS), Band 5155 von Lecture Notes in Computer Science, S. 121-136.
Springer,
2008.
Website anzeigen - 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), S. 20577-20584.
,
2024.
Website anzeigen - 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), S. 1-20.
PLRM,
2023.
Website anzeigen - 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), S. 12313-12320.
,
2023.
Website anzeigen - 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), S. 5730.
,
2023.
PDF anzeigen - 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), S. 2107-2116.
PMLR,
2022.
Website anzeigen - 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, S. 6770-6792.
PLMR,
2022.
Website anzeigen - 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), Band 12873 von Lecture Notes in Computer Science, S. 276-288.
Springer,
2021.
Website anzeigen - 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), S. 1248-1257.
PMLR,
2021.
Website anzeigen - 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), S. 12198-12206.
AAAI Press,
2021.
Website anzeigen | PDF anzeigen | Zusammenfassung anzeigen
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), Band 12873 von Lecture Notes in Computer Science, S. 271-275.
Springer,
2021.
Website anzeigen | Zusammenfassung anzeigen
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.
- 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, S. 10302-10309.
AAAI Press,
2020.
Website anzeigen | PDF anzeigen | Zusammenfassung anzeigen
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.
- 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.
PDF anzeigen - 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, Band vol. 10820 von LNCS, S. 29-60.
Springer,
2018.
Website anzeigen | Zusammenfassung anzeigen
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:
Algorithm Substitution Attacks from a Steganographic Perspective.
In Proc. 24th ACM Conference on Computer and Communications Security (CCS 2017), S. 1649-1660.
ACM Press,
2017.
Website anzeigen | Zusammenfassung anzeigen
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), S. 1749-1755.
AAAI Press,
2017.
Website anzeigen | Zusammenfassung anzeigen
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.
- 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.
Website anzeigen | Zusammenfassung anzeigen
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, S. 387-394.
ACM (Awarded Best Student Paper),
2016.
Website anzeigen | Zusammenfassung anzeigen
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.
- 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), S. 1214-1222.
JMLR Proceedings,
2016.
Website anzeigen - 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, S. 3315-3321.
AAAI Press,
2016.
Website anzeigen - 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), Band 9472 von Lecture Notes in Computer Science, S. 151-162.
Springer,
2015.
Website anzeigen | Zusammenfassung anzeigen
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.
- 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), S. 882-891.
AUAI Press,
2015.
PDF anzeigen - 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, S. 3243-3249.
AAAI Press / International Joint Conferences on Artificial Intelligence,
2015.
PDF anzeigen - 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.
Website anzeigen - 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), S. 129-136.
ACM Press,
2014.
Website anzeigen - 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, S. 907-916.
AUAI Press,
2014.
PDF anzeigen - 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, Band WP 13-01 von CTIT Workshop Proceedings, S. 159-162.
,
2013.
- Maciej Liskiewicz, Rüdiger Reischuk, Ulrich Wölfel:
Grey-Box Steganography.
Band 6648 von Lecture Notes in Computer Science, S. 390-402.
Springer Verlag, Heidelberg, in Proceedings 8. TAMC,
2011.
Website anzeigen - 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), S. 681-688.
AUAI Press,
2011.
PDF anzeigen | Website anzeigen - Maciej Liskiewicz, Johannes Textor:
Negative Selection Algorithms Without Generating Detectors.
In Proceedings of the 12th annual conference on Genetic and evolutionary computation (GECCO'10), S. 1047-1054.
ACM,
2010.
PDF anzeigen | Website anzeigen | Zusammenfassung anzeigen
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.
- Christian Hundt, Maciej Liskiewicz:
New Complexity Bounds for Image Matching under Rotation and Scaling.
In Proceedings of Symposium on Combinatorial Pattern Matching (CPM), Band 5577 von Lecture Notes in Computer Science, S. 127-141.
Springer,
2009.
Website anzeigen
