50 years Univerity of Lübeck

Prof. Dr. Till Tantau

Publications


Journal articles

  • Arfst Nickelsen, Till Tantau:
    Partial Information Classes.
    SIGACT News, 34(1):32--46, 2003.
    Go to website | Show abstract
  • Till Tantau:
    Query Complexity of Membership Comparable Sets.
    Theoretical Computer Science, 302(1-3):467-474, 2003.
    Go to website | Show abstract
  • Mitsunori Ogihara, Till Tantau:
    On the Reducibility of Sets Inside NP to Sets with Low Information Content.
    Journal of Computer and System Sciences, 69(4):299-324, 2004.
    Show abstract
  • Till Tantau:
    Comparing Verboseness for Finite Automata and Turing Machines.
    Theory of Computing Systems, 37(1):95-109, 2004.
    Show abstract
  • Till Tantau:
    Strahlende Präsentationen in LaTeX.
    Die TeXnische Komödie, 2/04:54-80, 2004. In German.
    Go to website | Show abstract
  • Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau:
    Contextfree Languages Can Be Accepted With Absolutely No Space Overhead.
    Information and Computation, 203(2):163-180, 2005.
    Show abstract
  • Arfst Nickelsen, Till Tantau:
    The Complexity of Finding Paths in Graphs with Bounded Independence Number.
    SIAM Journal on Computing, 34(5):1176-1195, 2005.
    Show abstract
  • Till Tantau:
    Weak Cardinality Theorems.
    Journal of Symbolic Logic, 70(3):861-878, 2005.
    Show abstract
  • Jens Gramm, Till Nierhoff, Roded Sharan, Till Tantau:
    Haplotyping with Missing Data via Perfect Path Phylogenies.
    Discrete and Applied Mathematics, 155:788-805, 2007.
    Show abstract
  • Till Tantau:
    Logspace Optimization Problems and Their Approximability Properties.
    Theory of Computing Systems, 41(2):327-350, 2007.
    Show abstract
  • Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau:
    Dynamic Kernels for Hitting Sets and Set Packing.
    Algorithmica, 84:3459–3488, 2022.
    Go to website | Show abstract
  • Max Bannach, Till Tantau:
    On the Descriptive Complexity of Color Coding.
    MDPI Algorithms, 2021. Special Issue: Parameterized Complexity and Algorithms for Nonclassical Logics
    Go to website | Show abstract
  • Max Bannach, Till Tantau:
    Computing Hitting Set Kernels By AC^0-Circuits.
    Theory of Computing Systems, 64(3):374--399, 2020.
    Go to website | Show abstract
  • Michael Elberfeld, Martin Grohe, Till Tantau:
    Where First-Order and Monadic Second-Order Logic Coincide.
    Transactions on Computational Logic, (Volume 17 Issue 4, November 2016 Article No. 25)2016.
  • Till Tantau:
    A Gentle Introduction to Applications of Algorithmic Metatheorems for Space and Circuit Classes.
    Algorithms, 9(3):1-44, 2016.
    Go to website | Show abstract
  • Michael Elberfeld, Christoph Stockhusen, Till Tantau:
    On the Space and Circuit Complexity of Parameterized Problems: Classes and Completeness.
    Algorithmica, 71(3):661-701, 2015.
    Go to website | Show abstract
  • Till Tantau:
    Graph Drawing in TikZ.
    Journal of Graph Algorithms and Applications, 17(4):495-513, 2013.
    Show PDF | Show abstract
  • Valentina Damerow, Bodo Manthey, Friedhelm Meyer auf der Heide, Harald Räcke, Christian Scheideler, Christian Sohler, Till Tantau:
    Smoothed Analysis of Left-To-Right Maxima with Applications.
    ACM Transactions on Algorithms, 8(3):Article No. 30, 2012.
    Go to website | Show abstract
  • Michael Elberfeld, Ilka Schnoor, Till Tantau:
    Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data.
    Theoretical Computer Science, 432:38–51, 2012.
    Show PDF | Go to website | Show abstract
  • Michael Elberfeld, Till Tantau:
    Phylogeny- and Parsimony-Based Haplotype Inference with Constraints.
    Information and Computation, 213:33–47, 2012.
    Show PDF | Go to website | Show abstract
  • Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe:
    On the Complexity of Kings.
    Theoretical Computer Science, 411(2010):783-798, 2010.
    Go to website | Show abstract
  • Jens Gramm, Tzvika Hartman, Till Nierhoff, Roded Sharan, Till Tantau:
    On the complexity of SNP block partitioning under the perfect phylogeny model.
    Discrete Mathematics, 309(18):5610-5617, 2009.
    Go to website | Show abstract
  • Jens Gramm, Arfst Nickelsen, Till Tantau:
    Fixed-Parameter Algorithms in Phylogenetics.
    The Computer Journal, 51(1):79--101, 2008.
    Show PDF | Show abstract