50 Jahre Uni Lübeck

Prof. Dr. Till Tantau

Veröffentlichungen


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.
    PDF anzeigen | Zusammenfassung anzeigen
  • Michael Elberfeld, Martin Grohe, Till Tantau:
    Where First-Order and Monadic Second-Order Logic Coincide.
    Transactions on Computational Logic, 2016 (noch nicht erschienen). Accepted for publication
  • Till Tantau:
    A Gentle Introduction to Applications of Algorithmic Metatheorems for Space and Circuit Classes.
    Algorithms, 9(3):1-44, 2016.
    Website anzeigen | Zusammenfassung anzeigen

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.
    Website anzeigen | Zusammenfassung anzeigen
  • Michael Elberfeld, Christoph Stockhusen, Till Tantau:
    On the Space and Circuit Complexity of Parameterized Problems: Classes and Completeness.
    Algorithmica, 71(3):661-701, 2015.
    Website anzeigen | Zusammenfassung anzeigen
  • 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), Band 30 von Leibniz International Proceedings in Informatics (LIPIcs), S. 703-715. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2015.
    Website anzeigen | Zusammenfassung anzeigen

2013

  • Christoph Stockhusen, Till Tantau:
    Completeness Results for Parameterized Space Classes.
    Technischer Bericht arxiv:1308.2892, ArXiv, 2013.
    Website anzeigen | Zusammenfassung anzeigen
  • 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 (noch nicht erschienen).
    Zusammenfassung anzeigen
  • Till Tantau:
    Graph Drawing in TikZ.
    In Proceedings of Graph Drawing 2012, Band 7704 von Lecture Notes in Computer Science, S. 517-528. Springer, 2013.
    Zusammenfassung anzeigen
  • Till Tantau:
    Graph Drawing in TikZ.
    Journal of Graph Algorithms and Applications, 17(4):495-513, 2013.
    PDF anzeigen | Zusammenfassung anzeigen

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.
    Website anzeigen | Zusammenfassung anzeigen
  • 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), Band 14 von Leibniz International Proceedings in Informatics (LIPIcs), S. 66-77. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2012.
    PDF anzeigen | Website anzeigen | Zusammenfassung anzeigen
  • 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.
    PDF anzeigen | Website anzeigen | Zusammenfassung anzeigen
  • 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), Band 7535 von Lecture Notes in Computer Science, S. 206-217. Springer, 2012.
    Website anzeigen | Zusammenfassung anzeigen
  • Michael Elberfeld, Christoph Stockhusen, Till Tantau:
    On the Space Complexity of Parameterized Problems.
    Technischer Bericht , ECCC, 2012.
    Website anzeigen | PDF anzeigen | Zusammenfassung anzeigen
  • Michael Elberfeld, Till Tantau:
    Phylogeny- and Parsimony-Based Haplotype Inference with Constraints.
    Information and Computation, 213:33–47, 2012.
    PDF anzeigen | Website anzeigen | Zusammenfassung anzeigen
  • 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), S. 265-274. IEEE Computer Society, 2012.
    PDF anzeigen | Website anzeigen | Zusammenfassung anzeigen

2011

  • Michael Elberfeld, Andreas Jakoby, Till Tantau:
    Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth.
    Technischer Bericht ECCC-TR11-128, Electronic Colloquium on Computational Complexity, 2011.
    PDF anzeigen | Website anzeigen | Zusammenfassung anzeigen

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), S. 143-152. IEEE Computer Society, 2010.
    Website anzeigen | Zusammenfassung anzeigen
  • Michael Elberfeld, Andreas Jakoby, Till Tantau:
    Logspace Versions of the Theorems of Bodlaender and Courcelle.
    Technischer Bericht ECCC-TR10-062, Electronic Colloquium on Computational Complexity, 2010.
    PDF anzeigen | Website anzeigen | Zusammenfassung anzeigen
  • Michael Elberfeld, Till Tantau:
    Phylogeny- and Parsimony-Based Haplotype Inference with Constraints.
    Technischer Bericht SIIM-TR-A-10-01, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2010.
    PDF anzeigen | Zusammenfassung anzeigen
  • 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), Band 6129 von Lecture Notes in Computer Science, S. 177-189. Springer, 2010.
    Website anzeigen | Zusammenfassung anzeigen
  • Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe:
    On the Complexity of Kings.
    Theoretical Computer Science, 411(2010):783-798, 2010.
    Website anzeigen | Zusammenfassung anzeigen

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), Band 5532 von Lecture Notes in Computer Science, S. 201-210. Springer, 2009.
    PDF anzeigen | Website anzeigen | Zusammenfassung anzeigen
  • 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.
    Website anzeigen | Zusammenfassung anzeigen

2008

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

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.
    Zusammenfassung anzeigen
  • Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe:
    On the Complexity of Kings.
    In Proceedings of FCT 2007, Band 4639 von Lecture Notes in Computer Science, S. 328--340. Springer, 2007.
    Zusammenfassung anzeigen
  • 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), Band 4855 von Lecture Notes in Computer Science, S. 216-227. Springer, 2007.
    Zusammenfassung anzeigen
  • Bodo Manthey, Till Tantau:
    Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise.
    Technischer Bericht ECCC-TR07-039, Electronic Colloquium on Computational Complexity, 2007.
    Website anzeigen | Zusammenfassung anzeigen
  • Till Tantau:
    Logspace Optimization Problems and Their Approximability Properties.
    Theory of Computing Systems, 41(2):327-350, 2007.
    Zusammenfassung anzeigen

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), Band 4175 von Lecture Notes in Computer Science, S. 92-102. Springer, 2006.
    Zusammenfassung anzeigen
  • Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe:
    On the Complexity of Kings.
    Technischer Bericht URCS-TR905, Technische Berichtsreihe der Universität Rochester, Computer Science Department, 2006.
    Website anzeigen | Zusammenfassung anzeigen
  • 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, Band 3895 von Lecture Notes in Computer Science - Festschriften, S. 111-128. Springer, 2006.
    Zusammenfassung anzeigen
  • Till Tantau:
    The Descriptive Complexity of the Reachability Problem As a Function of Different Graph Parameters.
    Technischer Bericht ECCC-TR06-035, Electronic Colloquium on Computational Complexity, 2006.
    Website anzeigen | Zusammenfassung anzeigen

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.
    Zusammenfassung anzeigen
  • 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), Band 19 von Electronic Notes in Discrete Mathematics, S. 225-231. Springer, 2005.
    Zusammenfassung anzeigen
  • Arfst Nickelsen, Till Tantau:
    The Complexity of Finding Paths in Graphs with Bounded Independence Number.
    SIAM Journal on Computing, 34(5):1176-1195, 2005.
    Zusammenfassung anzeigen
  • Till Tantau:
    Logspace Optimization Problems and Their Approximability Properties.
    In Proceedings of the 15th International Symposium on Fundamentals of Computation Theory (FCT 2005), Band 3623 von Lecture Notes in Computer Science, S. 92-103. Springer, 2005.
    Zusammenfassung anzeigen
  • Till Tantau:
    Weak Cardinality Theorems.
    Journal of Symbolic Logic, 70(3):861-878, 2005.
    Zusammenfassung anzeigen

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, S. 35-46. , 2004.
    Zusammenfassung anzeigen
  • 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, Band 3162 von Lecture Notes in Computer Science, S. 174-186. Springer, 2004.
    Zusammenfassung anzeigen
  • Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau:
    Overhead-Free Computation, DCFLs, and CFLs.
    Technischer Bericht URCS-TR-2004-844, Technische Berichtsreihe der Universität Rochester, Computer Science Department, 2004.
    Website anzeigen | Zusammenfassung anzeigen
  • Arfst Nickelsen, Till Tantau, Lorenz Weizäcker:
    Aggregates with Component Size One Characterize Polynomial Space.
    Technischer Bericht ECCC-TR04-028, Electronic Colloquium on Computational Complexity, 2004.
    Website anzeigen | Zusammenfassung anzeigen
  • 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.
    Zusammenfassung anzeigen
  • Till Tantau:
    Comparing Verboseness for Finite Automata and Turing Machines.
    Theory of Computing Systems, 37(1):95-109, 2004.
    Zusammenfassung anzeigen
  • Till Tantau:
    Strahlende Präsentationen in LaTeX.
    Die TeXnische Komödie, 2/04:54-80, 2004. In German.
    Website anzeigen | Zusammenfassung anzeigen
  • Till Tantau:
    Über strukturelle Gemeinsamkeiten der Aufzählbarkeitsklassen von Turingmaschinen und endlichen Automaten.
    In Ausgezeichnete Informatikdissertationen 2003, Lecture Notes in Informatics, S. 189-198. Springer, 2004.
    Zusammenfassung anzeigen
  • 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), Band 2996 von Lecture Notes in Computer Science, S. 326-337. Springer, 2004.
    PDF anzeigen | Zusammenfassung anzeigen

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), Band 2710 von Lecture Notes in Computer Science, S. 325-336. Springer, 2003.
    Website anzeigen | Zusammenfassung anzeigen
  • Arfst Nickelsen, Till Tantau:
    Partial Information Classes.
    SIGACT News, 34(1):32--46, 2003.
    Website anzeigen | Zusammenfassung anzeigen
  • Till Tantau:
    Logspace Optimisation Problems and Their Approximation Properties.
    Technischer Bericht ECCC-TR03-077, Electronic Colloquium on Computational Complexity, 2003.
    Website anzeigen | Zusammenfassung anzeigen
  • Till Tantau:
    On Structural Similarities of Finite Automata and Turing Machine Enumerability Classes.
    Wissenschaft und Technik Verlag, 2003.
    Gutachter: Dirk Siefkes, Johannes Köbler. Disseration zum Dr. rer. nat., Technische Universität Berlin
    Zusammenfassung anzeigen
  • Till Tantau:
    Query Complexity of Membership Comparable Sets.
    Theoretical Computer Science, 302(1-3):467-474, 2003.
    Website anzeigen | Zusammenfassung anzeigen
  • Till Tantau:
    Weak Cardinality Theorems for First-Order Logic.
    Technischer Bericht ECCC-TR03-024, Electronic Colloquium on Computational Complexity, 2003.
    Website anzeigen | Zusammenfassung anzeigen
  • Till Tantau:
    Weak Cardinality Theorems for First-Order Logic.
    In Proceedings of the 14th International Symposium on Fundamentals of Computation Theory (FCT 2003), Band 2751 von Lecture Notes in Computer Science, S. 400-411. Springer, 2003.
    Website anzeigen | Zusammenfassung anzeigen

2002

  • Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau:
    Computation with Absolutely No Overhead.
    Technischer Bericht URCS-TR-2002-779, Technische Berichtsreihe der Universität Rochester, Computer Science Department, 2002.
    Website anzeigen | Zusammenfassung anzeigen
  • 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), Band 2387 von Lecture Notes in Computer Science, S. 554--563. Springer, 2002.
    Zusammenfassung anzeigen
  • Mitsunori Ogihara, Till Tantau:
    On the Reducibility of Sets Inside NP to Sets with Low Information Content.
    Technischer Bericht URCS-TR-2002-782, Technische Berichtsreihe der Universität Rochester, Computer Science Department, 2002.
    Website anzeigen | Zusammenfassung anzeigen
  • Till Tantau:
    A Note on the Power of Extra Queries to Membership Comparable Sets.
    Technischer Bericht ECCC-TR02-044, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2002.
    Website anzeigen | Zusammenfassung anzeigen
  • 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), Band 2285 von Lecture Notes in Computer Science, S. 465-476. Springer, 2002.
    Website anzeigen | Zusammenfassung anzeigen
  • Till Tantau:
    Towards a Cardinality Theorem for Finite Automata.
    In Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science (MFCS 2002), Band 2420 von Lecture Notes in Computer Science, S. 625-636. Springer, 2002.
    Website anzeigen | Zusammenfassung anzeigen

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), Band 2138 von Lecture Notes in Computer Science, S. 299-310. Springer, 2001.
    Website anzeigen | Zusammenfassung anzeigen
  • Till Tantau:
    A Note on the Complexity of the Reachability Problem for Tournaments.
    Technischer Bericht ECCC-TR01-092, Electronic Colloquium on Computational Complexity, 2001.
    Website anzeigen | Zusammenfassung anzeigen
  • Till Tantau:
    Schnelle Löser für periodische Integralgleichungen mittels Matrixkompression und Mehrgitteriteration.
    Technische Universität Berlin, 2001. Diplomarbeit Mathematik
    Zusammenfassung anzeigen

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, Band 1868 von Lecture Notes in Computer Science, S. 146--164. Springer, 2000.
    Zusammenfassung anzeigen
  • Till Tantau:
    On the Power of Extra Queries to Selective Languages.
    Technischer Bericht ECCC-TR00-077, Electronic Colloquium on Computational Complexity, 2000.
    Website anzeigen | Zusammenfassung anzeigen