50 years Univerity of Lübeck

Prof. Dr. Till Tantau

Publications


2022

  • 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, Malte Skambath, Till Tantau:
    On the Parallel Parameterized Complexity of MaxSAT Variants.
    In Proceedings of the 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022), LIPIcs, 2022.
    Go to website

2021

  • Max Bannach, Zacharias Heinrich, Till Tantau, Rüdiger Reischuk:
    Dynamic Kernels for Hitting Sets and Set Packing.
    In Proceedings of the 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), Volume 214 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
    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

2020

  • 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
  • Max Bannach, Malte Skambath, Till Tantau:
    Kernelizing the Hitting Set Problem in Linear Sequential and Constant Parallel Time.
    In Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020), LIPIcs, 2020.
    Go to website | Show abstract

2019

  • Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau:
    Dynamic Kernels for Hitting Sets and Set Packing.
    Technical report , Electronic Colloquium on Computational Complexity, 2019.
    Go to website | Show abstract
  • Max Bannach, Till Tantau:
    On the Descriptive Complexity of Color Coding.
    In Proceedings of STACS 2019, LIPIcs, LIPIcs, 2019.
    Go to website | Show PDF | Show abstract
  • Max Bannach, Malte Skambath, Till Tantau:
    Towards Work-Efficient Parallel Parameterized Algorithms.
    In Proceedings of the 13th International Conference and Workshops on Algorithms and Computation (WALCOM 2019), Springer, 2019.
    Go to website | Show PDF | Show abstract

2018

  • Max Bannach, Till Tantau:
    Computing Hitting Set Kernels By AC^0-Circuits.
    In Proceedings of the 35th International Symposium on Theoretical Aspects of Computer Science, LIPIcs, 2018.
    Go to website | Show PDF | Show abstract
  • Max Bannach, Till Tantau:
    Computing Kernels in Parallel: Lower and Upper Bounds.
    In Proceedings of the 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), LIPIcs, 2018.
    Go to website | Show PDF | Show abstract

2017

  • Till Tantau:
    Applications of Algorithmic Metatheorems to Space Complexity and Parallelism (Invited Talk)..
    In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), pp. 4:1--4:4. DROPS, 2017.
    Go to website | Show abstract

2016

  • Max Bannach, Till Tantau:
    Parallel Multivariate Meta-Theorems.
    In Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC 2016), LIPIcs, 2016.
    Go to website | Show PDF | 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.
  • Malte Skambath, Till Tantau:
    Offline Drawing of Dynamic Trees: Algorithmics and Document Integration.
    In GD 2016: Graph Drawing and Network Visualization, Volume 9801 of LNCS, pp. 572-586. Springer, 2016.
    Go to website | Show abstract
  • Malte Skambath, Till Tantau:
    Offline Drawing of Dynamic Trees: Algorithmics and Document Integration Analysis of Binary Search Trees.
    Technical report arXiv:1608.08385, CoRR, 2016.
    Go to website | Show abstract
  • 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

2015

  • Max Bannach, Christoph Stockhusen, Till Tantau:
    Fast Parallel Fixed-Parameter Algorithms via Color Coding.
    In Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), LIPIcs, 2015.
    Go to website | Show PDF | 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:
    Existential Second-order Logic over Graphs: A Complete Complexity-theoretic Classification.
    In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), Volume 30 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 703-715. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2015.
    Go to website | Show abstract

2013

  • Christoph Stockhusen, Till Tantau:
    Completeness Results for Parameterized Space Classes.
    Technical report arxiv:1308.2892, ArXiv, 2013.
    Go to website | Show abstract
  • Christoph Stockhusen, Till Tantau:
    Completeness Results for Parameterized Space Classes.
    In 8th International Symposium on Parameterized and Exact Computation (IPEC 2013), Lecture Notes in Computer Science, Springer, 2013 (to appear).
    Show abstract
  • Till Tantau:
    Graph Drawing in TikZ.
    In Proceedings of Graph Drawing 2012, Volume 7704 of Lecture Notes in Computer Science, pp. 517-528. Springer, 2013.
    Show abstract
  • Till Tantau:
    Graph Drawing in TikZ.
    Journal of Graph Algorithms and Applications, 17(4):495-513, 2013.
    Show PDF | Show abstract

2012

  • 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, Andreas Jakoby, Till Tantau:
    Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth.
    In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), Volume 14 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 66-77. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2012.
    Show PDF | 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, Christoph Stockhusen, Till Tantau:
    On the Space Complexity of Parameterized Problems.
    In Proceedings of the 7th International Symposium on Parameterized and Exact Computation (IPEC 2012), Volume 7535 of Lecture Notes in Computer Science, pp. 206-217. Springer, 2012.
    Go to website | Show abstract
  • Michael Elberfeld, Christoph Stockhusen, Till Tantau:
    On the Space Complexity of Parameterized Problems.
    Technical report , ECCC, 2012.
    Go to website | Show PDF | 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
  • Michael Elberfeld, Martin Grohe, Till Tantau:
    Where First-Order and Monadic Second-Order Logic Coincide.
    In Proceedings of the 27th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2012), pp. 265-274. IEEE Computer Society, 2012.
    Show PDF | Go to website | Show abstract

2011

  • Michael Elberfeld, Andreas Jakoby, Till Tantau:
    Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth.
    Technical report ECCC-TR11-128, Electronic Colloquium on Computational Complexity, 2011.
    Show PDF | Go to website | Show abstract

2010

  • Michael Elberfeld, Andreas Jakoby, Till Tantau:
    Logspace Versions of the Theorems of Bodlaender and Courcelle.
    In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010), pp. 143-152. IEEE Computer Society, 2010.
    Go to website | Show abstract
  • Michael Elberfeld, Andreas Jakoby, Till Tantau:
    Logspace Versions of the Theorems of Bodlaender and Courcelle.
    Technical report ECCC-TR10-062, Electronic Colloquium on Computational Complexity, 2010.
    Show PDF | Go to website | Show abstract
  • Michael Elberfeld, Till Tantau:
    Phylogeny- and Parsimony-Based Haplotype Inference with Constraints.
    Technical report SIIM-TR-A-10-01, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2010.
    Show PDF | Show abstract
  • Michael Elberfeld, Till Tantau:
    Phylogeny- and Parsimony-Based Haplotype Inference with Constraints.
    In Proceedings of the 21st Annual Symposium on Combinatorial Pattern Matching (CPM 2010), Volume 6129 of Lecture Notes in Computer Science, pp. 177-189. Springer, 2010.
    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

2009

  • Michael Elberfeld, Ilka Schnoor, Till Tantau:
    Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data.
    In Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation (TAMC 2009), Volume 5532 of Lecture Notes in Computer Science, pp. 201-210. Springer, 2009.
    Show PDF | 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

2008

  • Jens Gramm, Arfst Nickelsen, Till Tantau:
    Fixed-Parameter Algorithms in Phylogenetics.
    In Bioinformatics: Volume I: Data, Sequence Analysis and Evolution, Volume 452 of Methods in Molecular Biology, pp. 507-535. Springer, 2008.
    Show abstract
  • Bodo Manthey, Till Tantau:
    Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise.
    In Proceedings of MFCS 2008, Volume 5162 of Lecture Notes in Computer Science, pp. 467-478. Springer, 2008.
    Show abstract
  • Till Tantau:
    Complexity of the Undirected Radius and Diameter Problems for Succinctly Represented Graphs.
    Technical report SIIM-TR-A-08-03, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2008.
    Show PDF
  • Till Tantau:
    Der One-Time-Pad-Algorithmus.
    In Taschenbuch der Algorithmen, Springer, 2008.
    Show abstract
  • Till Tantau:
    Generalizations of the Hartmanis-Immerman-Sewelson Theorem and Applications to Infinite Subsets of P-Selective Sets.
    Technical report ECCC-TR08-027, Electronic Colloquium on Computational Complexity, 2008.
    Show PDF | Show abstract
  • Michael Elberfeld, Till Tantau:
    Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems.
    Technical report SIIM-TR-A-08-02, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2008.
    Show PDF | Show abstract
  • Michael Elberfeld, Till Tantau:
    Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems.
    In Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2008), Volume 5162 of Lecture Notes in Computer Science, pp. 299-310. Springer, 2008.
    Go to website | Show abstract
  • Michael Elberfeld, Ilka Schnoor, Till Tantau:
    Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data.
    Technical report SIIM-TR-A-08-05, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2008.
    Show PDF | 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

2007

  • 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
  • Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe:
    On the Complexity of Kings.
    In Proceedings of FCT 2007, Volume 4639 of Lecture Notes in Computer Science, pp. 328--340. Springer, 2007.
    Show abstract
  • Andreas Jakoby, Till Tantau:
    Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs.
    In Proceedings of the 27th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2007), Volume 4855 of Lecture Notes in Computer Science, pp. 216-227. Springer, 2007.
    Show abstract
  • Bodo Manthey, Till Tantau:
    Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise.
    Technical report ECCC-TR07-039, Electronic Colloquium on Computational Complexity, 2007.
    Go to website | Show abstract
  • Till Tantau:
    Logspace Optimization Problems and Their Approximability Properties.
    Theory of Computing Systems, 41(2):327-350, 2007.
    Show abstract

2006

  • Jens Gramm, Tzvika Hartman, Till Nierhoff, Roded Sharan, Till Tantau:
    On the Complexity of SNP Block Partitioning Under the Perfect Phylogeny Model.
    In Proceedings of Workshop on Algorithms in Bioinformatics (WABI), Volume 4175 of Lecture Notes in Computer Science, pp. 92-102. Springer, 2006.
    Show abstract
  • Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe:
    On the Complexity of Kings.
    Technical report URCS-TR905, Technische Berichtsreihe der Universität Rochester, Computer Science Department, 2006.
    Go to website | Show abstract
  • Richard Karp, Till Nierhoff, Till Tantau:
    Optimal Flow Distribution Among Multiple Channels with Unknown Capacities.
    In Essays in Theoretical Computer Science in Memory of Shimon Even, Volume 3895 of Lecture Notes in Computer Science - Festschriften, pp. 111-128. Springer, 2006.
    Show abstract
  • Till Tantau:
    The Descriptive Complexity of the Reachability Problem As a Function of Different Graph Parameters.
    Technical report ECCC-TR06-035, Electronic Colloquium on Computational Complexity, 2006.
    Go to website | Show abstract

2005

  • 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
  • Richard Karp, Till Nierhoff, Till Tantau:
    Optimal Flow Distribution Among Multiple Channels with Unknown Capacities.
    In Proceedings of the 2nd Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO 2005), Volume 19 of Electronic Notes in Discrete Mathematics, pp. 225-231. Springer, 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:
    Logspace Optimization Problems and Their Approximability Properties.
    In Proceedings of the 15th International Symposium on Fundamentals of Computation Theory (FCT 2005), Volume 3623 of Lecture Notes in Computer Science, pp. 92-103. Springer, 2005.
    Show abstract
  • Till Tantau:
    Weak Cardinality Theorems.
    Journal of Symbolic Logic, 70(3):861-878, 2005.
    Show abstract

2004

  • Jens Gramm, Till Nierhoff, Roded Sharan, Till Tantau:
    On the Complexity of Haplotyping via Perfect Phylogeny.
    In Proceedings of Second RECOMB Satellite Workshop on Computational Methods for SNPs and Haplotypes, pp. 35-46. , 2004.
    Show abstract
  • Jens Gramm, Till Nierhoff, Till Tantau:
    Perfect Path Phylogeny Haplotyping with Missing Data is Fixed-Parameter Tractable.
    In Proceedings of the 2004 International Workshop on Parameterized and Exact Computation, Volume 3162 of Lecture Notes in Computer Science, pp. 174-186. Springer, 2004.
    Show abstract
  • Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau:
    Overhead-Free Computation, DCFLs, and CFLs.
    Technical report URCS-TR-2004-844, Technische Berichtsreihe der Universität Rochester, Computer Science Department, 2004.
    Go to website | Show abstract
  • Arfst Nickelsen, Till Tantau, Lorenz Weizäcker:
    Aggregates with Component Size One Characterize Polynomial Space.
    Technical report ECCC-TR04-028, Electronic Colloquium on Computational Complexity, 2004.
    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
  • Till Tantau:
    Über strukturelle Gemeinsamkeiten der Aufzählbarkeitsklassen von Turingmaschinen und endlichen Automaten.
    In Ausgezeichnete Informatikdissertationen 2003, Lecture Notes in Informatics, pp. 189-198. Springer, 2004.
    Show abstract
  • Till Tantau:
    A Logspace Approximation Scheme for the Shortest Path Problem for Graphs with Bounded Independence Number.
    In Proceedings of the 21st International Symposium on Theoretical Aspects of Computer Science (STACS 2004), Volume 2996 of Lecture Notes in Computer Science, pp. 326-337. Springer, 2004.
    Show PDF | Show abstract

2003

  • Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau:
    Computation with Absolutely No Space Overhead.
    In Proceedings of the Seventh International Conference on Developments in Language Theory (DLT 2003), Volume 2710 of Lecture Notes in Computer Science, pp. 325-336. Springer, 2003.
    Go to website | Show abstract
  • Arfst Nickelsen, Till Tantau:
    Partial Information Classes.
    SIGACT News, 34(1):32--46, 2003.
    Go to website | Show abstract
  • Till Tantau:
    Logspace Optimisation Problems and Their Approximation Properties.
    Technical report ECCC-TR03-077, Electronic Colloquium on Computational Complexity, 2003.
    Go to website | Show abstract
  • Till Tantau:
    On Structural Similarities of Finite Automata and Turing Machine Enumerability Classes.
    Wissenschaft und Technik Verlag, 2003.
    Supervised by: Dirk Siefkes, Johannes Köbler. Disseration zum Dr. rer. nat., Technische Universität Berlin
    Show abstract
  • Till Tantau:
    Query Complexity of Membership Comparable Sets.
    Theoretical Computer Science, 302(1-3):467-474, 2003.
    Go to website | Show abstract
  • Till Tantau:
    Weak Cardinality Theorems for First-Order Logic.
    Technical report ECCC-TR03-024, Electronic Colloquium on Computational Complexity, 2003.
    Go to website | Show abstract
  • Till Tantau:
    Weak Cardinality Theorems for First-Order Logic.
    In Proceedings of the 14th International Symposium on Fundamentals of Computation Theory (FCT 2003), Volume 2751 of Lecture Notes in Computer Science, pp. 400-411. Springer, 2003.
    Go to website | Show abstract

2002

  • Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau:
    Computation with Absolutely No Overhead.
    Technical report URCS-TR-2002-779, Technische Berichtsreihe der Universität Rochester, Computer Science Department, 2002.
    Go to website | Show abstract
  • Arfst Nickelsen, Till Tantau:
    On Reachability in Graphs with Bounded Independence Number.
    In Proceedings of the Eighth Annual International Computing and Combinatorics Conference (COCOON 2002), Volume 2387 of Lecture Notes in Computer Science, pp. 554--563. Springer, 2002.
    Show abstract
  • Mitsunori Ogihara, Till Tantau:
    On the Reducibility of Sets Inside NP to Sets with Low Information Content.
    Technical report URCS-TR-2002-782, Technische Berichtsreihe der Universität Rochester, Computer Science Department, 2002.
    Go to website | Show abstract
  • Till Tantau:
    A Note on the Power of Extra Queries to Membership Comparable Sets.
    Technical report ECCC-TR02-044, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2002.
    Go to website | Show abstract
  • Till Tantau:
    Comparing Verboseness for Finite Automata and Turing Machines.
    In Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science (STACS 2002), Volume 2285 of Lecture Notes in Computer Science, pp. 465-476. Springer, 2002.
    Go to website | Show abstract
  • Till Tantau:
    Towards a Cardinality Theorem for Finite Automata.
    In Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science (MFCS 2002), Volume 2420 of Lecture Notes in Computer Science, pp. 625-636. Springer, 2002.
    Go to website | Show abstract

2001

  • Arfst Nickelsen, Till Tantau:
    Closure of Polynomial Time Partial Information Classes under Polynomial Time Reductions.
    In Proceedings of the 13th International Symposium on Fundamentals of Computation Theory (FCT 2001), Volume 2138 of Lecture Notes in Computer Science, pp. 299-310. Springer, 2001.
    Go to website | Show abstract
  • Till Tantau:
    A Note on the Complexity of the Reachability Problem for Tournaments.
    Technical report ECCC-TR01-092, Electronic Colloquium on Computational Complexity, 2001.
    Go to website | Show abstract
  • Till Tantau:
    Schnelle Löser für periodische Integralgleichungen mittels Matrixkompression und Mehrgitteriteration.
    Technische Universität Berlin, 2001. Diplomarbeit Mathematik
    Show abstract

2000

  • Klaus Didrich, Wolfgang Grieskamp, Florian Schintke, Till Tantau, Baltasar Trancón-y-Widemann:
    Reflections in Opal - Meta Information in a Functional Programming Language.
    In Proceedings of the 11th International Workshop on Implementation of Functional Languages, Lochem, The Netherlands, September 1999, (IFL'99), Selected Papers, Volume 1868 of Lecture Notes in Computer Science, pp. 146--164. Springer, 2000.
    Show abstract
  • Till Tantau:
    On the Power of Extra Queries to Selective Languages.
    Technical report ECCC-TR00-077, Electronic Colloquium on Computational Complexity, 2000.
    Go to website | Show abstract