Institute of Theoretical Computer Science

Research output

Research output per year 1996 2009 2011 2012 2013 2014 2015 2016 2017 2018 2020 2023

• 469 Citations
• 76 Bachelor Theses
• 60 Conference contribution
• 49 Master Theses
• 43 Journal articles
• 60 More
  • 15 Conference Papers
  • 12 Doctoral Theses
  • 10 Collected editions
  • 8 Contributions to collected editions/anthologies
  • 5 Other
  • 3 Chapter
  • 1 Books
  • 1 Commissioned Reports
  • 1 Conference proceedings
  • 1 Letters
  • 1 Newspaper articles
  • 1 Scientific review articles
  • 1 Preprint

Research output per year

Research output per year

Search results

• 2023

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

  Wienöbst, M., Bannach, M. & Liskiewicz, M., 2023, In: J. Mach. Learn. Res.. 24, p. 213:1-213:45

  Research output: Journal Articles › Journal articles › Research › peer-review
• 2022

  A Digital Therapeutic Allowing a Personalized Low-Glycemic Nutrition for the Prophylaxis of Migraine: Real World Data from Two Prospective Studies

  Lelleck, V. V., Schulz, F., Witt, O., Kühn, G., Klein, D., Gendolla, A., Evers, S., Gaul, C., Thaçi, D., Sina, C. & Schröder, T., 07.2022, In: Nutrients. 14, 14, 2927.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Migraine Disorders 100%
  • Prospective Studies 63%
  • Glucose 34%
  • Therapeutics 16%
  • Headache Disorders 13%
  2 Citations (Scopus)
• 2021

  A White-Box Masking Scheme Resisting Computational and Algebraic Attacks

  Seker, O., Eisenbarth, T. & Liskiewicz, M., 01.02.2021, In: IACR Transactions on Cryptographic Hardware and Embedded Systems. 2021, 2, p. 61–105

  Research output: Journal Articles › Journal articles › Research › peer-review
• 2020

  Computing Hitting Set Kernels By AC0-Circuits.

  Bannach, M. & Tantau, T., 2020, In: Theory Comput. Syst.. 64, 3, p. 374-399

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Networks (circuits) 100%
  • Parallel algorithms 85%

• Hardness of k-anonymous microaggregation

  Thaeter, F. & Reischuk, R., 27.10.2020, In: Discrete Applied Mathematics.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Microaggregation 100%
  • Hardness 57%
  • K-means Clustering 42%
  • K-means 39%
  • Clustering 27%

• New Bounds for the Vertices of the Integer Hull

  Berndt, S., Jansen, K. & Klein, K-M., 18.01.2020, In: CoRR. abs/2006.10847, 25 p.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Integer 100%
  • Concentration of Measure 54%
  • Linear Program 39%
  • Probability Theory 39%
  • Random variable 27%

• On the universal steganography of optimal rate

  Berndt, S. & Liśkiewicz, M., 12.2020, In: Information and Computation. 275, 104632.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Steganography 100%
  • Polynomials 32%
  • Entropy 17%
  • Bandwidth 13%

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

  Rosenke, C. & Liśkiewicz, M., 12.2020, In: Information and Computation. 275, 104550.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Image matching 100%
  • Optical character recognition 33%
  • Medical imaging 31%
  • Watermarking 31%
  • Image compression 28%
• 2019

  Sorting Signed Permutations by Inverse Tandem Duplication Random Losses

  Hartmann, T., Bannach, M. & Middendorf, M., 16.05.2019, In: IEEE/ACM Transactions on Computational Biology and Bioinformatics. p. 1 - 1 1 p.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Signed Permutations 100%
  • Duplication 87%
  • Sorting 78%
  • Gene 67%
  • Rearrangement 49%

• The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets

  Dannenberg, K., Jansson, J., Lingas, A. & Lundell, E. M., 31.03.2019, In: Discrete Applied Mathematics. 257, p. 101-114 14 p.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Approximability 100%
  • Fan 99%
  • Phylogenetic Tree 43%
  • Exponential time 37%
  • Leaves 33%
• 2018

  Computing Hitting Set Kernels By AC^0-Circuits

  Bannach, M. & Tantau, T., 2018, In: CoRR. abs/1801.00716

  Research output: Journal Articles › Journal articles › Research

  • Hitting Set 100%
  • Hypergraph 56%
  • kernel 49%
  • Computing 45%
  • Sunflower 22%
• 2017

  Security levels in steganography – Insecurity does not imply detectability

  Liśkiewicz, M., Reischuk, R. & Wölfel, U., 05.09.2017, In: Theoretical Computer Science. 692, p. 25-45 21 p.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Steganography 100%
• 2016

  A Gentle Introduction to Applications of Algorithmic Metatheorems for Space and Circuit Classes

  Tantau, T., 09.07.2016, In: Algorithms. 9, 3, 44.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Flavors 100%
  • Networks (circuits) 85%
  1 Citation (Scopus)

• Robust causal inference using directed acyclic graphs: The R package 'dagitty'

  Textor, J., van der Zander, B., Gilthorpe, M. S., Liskiewicz, M. & Ellison, G. TH., 01.12.2016, In: International Journal of Epidemiology. 45, 6, p. 1887-1894 8 p.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Mathematical Computing 100%
  • Epidemiologists 75%
  • Licensure 61%
  • Datasets 45%
  • Epidemiology 44%
  5 Citations (Scopus)

• Where first-order and monadic second-order logic coincide

  Elberfeld, M., Grohe, M. & Tantau, T., 11.2016, In: ACM Transactions on Computational Logic. 17, 4, 25.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Monadic Second-order Logic 100%
  • First-order 52%
  • Expressive Power 45%
  • First-order Logic 42%
  • Graph in graph theory 35%
  3 Citations (Scopus)
• 2014

  Activated CD4⁺ T cells enter the splenic T-cell zone and induce autoantibody-producing germinal centers through bystander activation

  Banczyk, D., Kalies, K., Nachbar, L., Bergmann, L., Schmidt, P., Bode, U., Teegen, B., Steven, P., Lange, T., Textor, J., Ludwig, R. J., Stöcker, W., König, P., Bell, E. & Westermann, J., 01.01.2014, In: European Journal of Immunology. 44, 1, p. 93-102 10 p.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Germinal Center 100%
  • Autoantibodies 77%
  • T-Lymphocytes 52%
  • B-Lymphocytes 24%
  • T-Lymphocyte Subsets 22%
  5 Citations (Scopus)

• A new upper bound for the traveling salesman problem in cubic graphs

  Liskiewicz, M. & Schuster, M. R., 07.2014, In: Journal of Discrete Algorithms. 27, p. 1-20 20 p.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Traveling salesman problem 100%
  5 Citations (Scopus)

• Existential Second-Order Logic Over Graphs: A Complete Complexity-Theoretic Classification

  Tantau, T., 2014, In: CoRR. abs/1412.6396

  Research output: Journal Articles › Journal articles › Research

  • Syntactics 100%
  • Computational complexity 79%
  • Constraint satisfaction problems 62%
  • Polynomials 37%

• On the Space and Circuit Complexity of Parameterized Problems: Classes and Completeness

  Elberfeld, M., Stockhusen, C. & Tantau, T., 16.10.2014, In: Algorithmica. 71, 3, p. 661-701 41 p.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Feedback 100%
  • Networks (circuits) 87%
  8 Citations (Scopus)

• Random Migration and Signal Integration Promote Rapid and Robust T Cell Recruitment

  Textor, J., Henrickson, S. E., Mandl, J. N., von Andrian, U. H., Westermann, J., de Boer, R. J. & Beltman, J. B., 07.08.2014, In: PLoS Computational Biology. 10, 8, e1003752.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Lymph Nodes 100%
  • T-Lymphocytes 86%
  • Antigens 22%
  • Photons 18%
  • Antigen-Presenting Cells 18%
  21 Citations (Scopus)
• 2013

  Approximation algorithms for orienting mixed graphs

  Elberfeld, M., Segev, D., Davidson, C. R., Silverbush, D. & Sharan, R., 29.04.2013, In: Theoretical Computer Science. 483, p. 96-103 8 p.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Mixed Graphs 100%
  • Approximation Algorithms 62%
  • Graph in graph theory 33%
  • Target 30%
  • Logarithmic 29%
  4 Citations (Scopus)

• Completeness Results for Parameterized Space Classes

  Stockhusen, C. & Tantau, T., 13.08.2013, In: CoRR. 26 p.

  Research output: Journal Articles › Journal articles › Research › peer-review

• Graph drawing in TikZ

  Tantau, T., 01.08.2013, In: Journal of Graph Algorithms and Applications. 17, 4, p. 495-513 19 p.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Typesetting 100%
  • Computer programming languages 54%
  • Profitability 53%
  • Labels 51%
  • Engines 38%
  2 Citations (Scopus)

• Grey-box steganography

  Liskiewicz, M., Reischuk, R. & Wölfel, U., 23.09.2013, In: Theoretical Computer Science. 505, p. 27-41 15 p.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Steganography 100%
  • Sampling 59%
  • Decision trees 20%
  • Machine learning 15%
  6 Citations (Scopus)
• 2012

  Improved Analysis of an Exact Algorithm for Cubic Graph TSP

  Liskiewicz, M. & Schuster, M. R., 2012, In: CoRR.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Traveling salesman problem 100%

• Influence of tree topology restrictions on the complexity of haplotyping with missing data

  Elberfeld, M., Schnoor, I. & Tantau, T., 11.05.2012, In: Theoretical Computer Science. 432, p. 38-51 14 p.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Phylogeny 100%
  • Topology 94%
  • Data acquisition 59%

• Phylogeny- and parsimony-based haplotype inference with constraints

  Elberfeld, M. & Tantau, T., 01.04.2012, In: Information and Computation. 213, p. 33-47 15 p.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Phylogeny 100%
  • Computational methods 36%
  • Polynomials 26%

• Smoothed analysis of left-to-right maxima with applications

  Damerow, V., Manthey, B., Heide, F. M. A. D., Racke, H., Scheideler, C., Sohler, C. & Tantau, T., 01.07.2012, In: ACM Transactions on Algorithms. 8, 3, 30.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Random Noise 100%
  • Quicksort 58%
  • Binary Search Tree 55%
  • Gaussian Noise 47%
  • Interval 45%
  4 Citations (Scopus)
• 2011

  A cryptographically t-private auction system

  Hinkelmann, M., Jakoby, A., Moebius, N., Rompf, T. & Stechert, P., 25.08.2011, In: Concurrency Computation Practice and Experience. 23, 12, p. 1399-1413 15 p.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Networks (circuits) 100%
  • Communication 30%
  4 Citations (Scopus)

• Defining the quantitative limits of intravital two-photon lymphocyte tracking

  Textor, J., Peixoto, A., Henrickson, S. E., Sinn, M., Von Andrian, U. H. & Westermann, J., 26.07.2011, In: Proceedings of the National Academy of Sciences of the United States of America. 108, 30, p. 12401-12406 6 p.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Photons 100%
  • Lymphocytes 65%
  • T-Lymphocytes 58%
  • Cell Movement 57%
  • Lymph Nodes 50%
  39 Citations (Scopus)

• Negative selection algorithms on strings with efficient training and linear-time classification

  Elberfeld, M. & Textor, J., 16.02.2011, In: Theoretical Computer Science. 412, 6, p. 534-542 9 p.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Detectors 100%
  • Classifiers 12%
  • Set theory 11%
  17 Citations (Scopus)

• New complexity bounds for image matching under rotation and scaling

  Hundt, C. & Liskiewicz, M., 01.03.2011, In: Journal of Discrete Algorithms. 9, 1, p. 122-136 15 p.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Image matching 100%
  • Pattern matching 18%
  • Chemical analysis 10%
  1 Citation (Scopus)

• On the approximability of reachability-preserving network orientations

  Elberfeld, M., Bafna, V., Gamzu, I., Medvedovsky, A., Segev, D., Silverbush, D., Zwick, U. & Sharan, R., 30.11.2011, In: Internet Mathematics. 7, 4, p. 209-232 24 p.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Approximability 100%
  • Reachability 92%
  • Graph in graph theory 26%
  • Approximation Algorithms 25%
  • Biological Networks 19%
  7 Citations (Scopus)

• Optimally orienting physical networks

  Silverbush, D., Elberfeld, M. & Sharan, R., 11.2011, In: Journal of Computational Biology. 18, 11, p. 1437-1448 12 p.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Proteins 100%
  • Direction compound 56%
  • Genes 46%
  • Causality 36%
  • Yeasts 31%
  10 Citations (Scopus)

• Privacy in Non-private Environments

  Bläser, M., Jakoby, A., Liskiewicz, M. & Manthey, B., 01.01.2011, In: Theory of Computing Systems. 48, 1, p. 211-245 35 p.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Network protocols 100%
  • Probability distributions 9%
  • Telecommunication networks 8%
  • Communication 4%
• 2010

  On the complexity of kings

  Hemaspaandra, E., Hemaspaandra, L. A., Tantau, T. & Watanabe, O., 28.01.2010, In: Theoretical Computer Science. 411, 4-5, p. 783-798 16 p.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Tournament 100%
  • Graph in graph theory 28%
  • Vertex of a graph 25%
  • Radius 24%
  • Overlay 20%
  1 Citation (Scopus)
• 2009

  A Combinatorial Geometric Approach to Two-dimensional Robustly Pattern Matching with Scaling and Rotation

  Hundt, C., Liskiewicz, M. & Nevries, R., 2009, In: Theoretical Computer Science. 2009, 51(410), p. 5317-5333

  Research output: Journal Articles › Journal articles › Research › peer-review

• Hybrid Simulation Algorithms for an Agent Based Model of the Immune Response

  Textor, J. & Hansen, B., 2009, In: Cybernetics and Systems. p. 390-417

  Research output: Journal Articles › Journal articles › Research › peer-review

• Improving the Average Delay of Sorting

  Jakoby, A., Liskiewicz, M., Reischuk, R. & Schindelhauer, C., 2009, In: Theoretical Computer Science. 2009, 410(11), p. 1030-1041

  Research output: Journal Articles › Journal articles › Research › peer-review

• Knowledge States for the Caching Problem in Shared Memory Multiprocessor Systems

  Bein, W., Marmore, L. L. & Reischuk, R., 2009, In: International Journal of Foundations of Computer Science. 2009, 20(1), p. 167-184

  Research output: Journal Articles › Journal articles › Research › peer-review

• On the complexity of SNP block partitioning under the perfect phylogeny model

  Gramm, J., Hartman, T., Niehoff, T., Sharan, R. & Tantau, T., 2009, In: Discrete Mathematics. 2009, 309(18), p. 5610-5617

  Research output: Journal Articles › Journal articles › Research › peer-review

• Privacy in Non-Private Environments

  Bläser, M., Jakoby, A., Liskiewicz, M. & Manthey, B., 2009, In: Theory of Computing Systems. 2009

  Research output: Journal Articles › Journal articles › Research › peer-review
• 2007

  Haplotyping with missing data via perfect path phylogenies

  Gramm, J., Nierhoff, T., Sharan, R. & Tantau, T., 01.04.2007, In: Discrete Applied Mathematics. 155, 6-7, p. 788-805 18 p.

  Research output: Journal Articles › Journal articles › Research › peer-review

  • Phylogeny 100%
  • Missing Data 80%
  • Path 52%
  • Genotype 39%
  • Haplotype 30%
  9 Citations (Scopus)