Till Tantau

110 papers A* 2A 12B 19C 3Misc 1Journal 60Unranked 9
YearRankTypeTitle / Venue / Authors
2026 J jnl
On the Complexity of Fundamental Problems for DAG-Compressed Graphs.
CoRR
Florian Chudigiewitsch, Till Tantau, Felix Winkler
2026 J jnl
The Descriptive Complexity of Relation Modification Problems.
CoRR
Florian Chudigiewitsch, Marlene Gründel, Christian Komusiewicz, Nils Morawietz, Till Tantau
2025 J jnl
Computational Complexity of Discrete Problems (Dagstuhl Seminar 25111).
Dagstuhl Reports
Swastik Kopparty, Meena Mahajan, Rahul Santhanam, Till Tantau, Ian Mertz
2024 A conf
Faster Graph Algorithms Through DAG Compression.
STACS
Max Bannach, Florian Andreas Marwitz, Till Tantau
2024 B conf
On the Descriptive Complexity of Vertex Deletion Problems.
MFCS
Max Bannach, Florian Chudigiewitsch, Till Tantau
2024 J jnl
On the Descriptive Complexity of Vertex Deletion Problems.
CoRR
Max Bannach, Florian Chudigiewitsch, Till Tantau
2024 J jnl
Seven Ways of Deciding Whether Most Vertex Sets Cover a Graph.
Bull. EATCS
Till Tantau
2023 J jnl
Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111).
Dagstuhl Reports
Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau, Manaswi Paraashar
2023 J jnl
Existential Second-Order Logic Over Graphs: Parameterized Complexity.
CoRR
Max Bannach, Florian Chudigiewitsch, Till Tantau
2023 B conf
Existential Second-Order Logic over Graphs: Parameterized Complexity.
IPEC
Max Bannach, Florian Chudigiewitsch, Till Tantau
2023 J jnl
On the Parallel Parameterized Complexity of MaxSAT Variants.
J. Artif. Intell. Res.
Max Bannach, Malte Skambath, Till Tantau
2022 B conf
An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions.
CPM
Laurent Bulteau, Mark Jones, Rolf Niedermeier, Till Tantau
2022 J jnl
Dynamic Kernels for Hitting Sets and Set Packing.
Algorithmica
Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau
2022 A conf
On the Parallel Parameterized Complexity of MaxSAT Variants.
SAT
Max Bannach, Malte Skambath, Till Tantau
2022 J jnl
On the Parallel Parameterized Complexity of MaxSAT Variants.
CoRR
Max Bannach, Malte Skambath, Till Tantau
2022 A conf
On the Satisfaction Probability of k-CNF Formulas.
CCC
Till Tantau
2022 J jnl
On the Satisfaction Probability of k-CNF Formulas.
CoRR
Till Tantau
2021 J jnl
Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121).
Dagstuhl Reports
Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau
2021 B conf
Dynamic Kernels for Hitting Sets and Set Packing.
IPEC
Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau
2021 — conf
Informatik fürs Leben lernen.
INFOS
Till Tantau
2021 J jnl
On the Descriptive Complexity of Color Coding.
Algorithms
Max Bannach, Till Tantau
2021 B conf
Work-sensitive Dynamic Complexity of Formal Languages.
FoSSaCS
Jonas Schmidt, Thomas Schwentick, Till Tantau, Nils Vortmeier, Thomas Zeume
2021 J jnl
Work-sensitive Dynamic Complexity of Formal Languages.
CoRR
Jonas Schmidt, Thomas Schwentick, Till Tantau, Nils Vortmeier, Thomas Zeume
2020 J jnl
Computing Hitting Set Kernels By AC
Theory Comput. Syst.
Max Bannach, Till Tantau
2020 — conf
Kernelizing the Hitting Set Problem in Linear Sequential and Constant Parallel Time.
SWAT
Max Bannach, Malte Skambath, Till Tantau
2019 J jnl
Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121).
Dagstuhl Reports
Anna Gál, Rahul Santhanam, Till Tantau
2019 J jnl
Dynamic Kernels for Hitting Sets and Set Packing.
Electron. Colloquium Comput. Complex.
Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau
2019 A conf
On the Descriptive Complexity of Color Coding.
STACS
Max Bannach, Till Tantau
2019 J jnl
On the Descriptive Complexity of Color Coding.
CoRR
Max Bannach, Till Tantau
2019 B conf
Towards Work-Efficient Parallel Parameterized Algorithms.
WALCOM
Max Bannach, Malte Skambath, Till Tantau
2019 J jnl
Towards Work-Efficient Parallel Parameterized Algorithms.
CoRR
Max Bannach, Malte Skambath, Till Tantau
2018 A conf
Computing Hitting Set Kernels By AC^0-Circuits.
STACS
Max Bannach, Till Tantau
2018 J jnl
Computing Hitting Set Kernels By AC^0-Circuits.
CoRR
Max Bannach, Till Tantau
2018 B conf
Computing Kernels in Parallel: Lower and Upper Bounds.
IPEC
Max Bannach, Till Tantau
2018 J jnl
Computing Kernels in Parallel: Lower and Upper Bounds.
CoRR
Max Bannach, Till Tantau
2018 — conf
Study Program "Robotics and Autonomous Systems" at the University of Lübeck.
EWME
Christian Herzog né Hoffmann, Till Tantau, Philipp Rostalski
2017 A conf
Applications of Algorithmic Metatheorems to Space Complexity and Parallelism (Invited Talk).
STACS
Till Tantau
2017 J jnl
Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121).
Dagstuhl Reports
Anna Gál, Michal Koucký, Oded Regev, Till Tantau
2016 J jnl
A Gentle Introduction to Applications of Algorithmic Metatheorems for Space and Circuit Classes.
Algorithms
Till Tantau
2016 A conf
Offline Drawing of Dynamic Trees: Algorithmics and Document Integration.
GD
Malte Skambath, Till Tantau
2016 J jnl
Offline Drawing of Dynamic Trees: Algorithmics and Document Integration.
CoRR
Malte Skambath, Till Tantau
2016 B conf
Parallel Multivariate Meta-Theorems.
IPEC
Max Bannach, Till Tantau
2016 J jnl
Where First-Order and Monadic Second-Order Logic Coincide.
ACM Trans. Comput. Log.
Michael Elberfeld, Martin Grohe, Till Tantau
2015 A conf
Existential Second-order Logic over Graphs: A Complete Complexity-theoretic Classification.
STACS
Till Tantau
2015 J jnl
Fast Parallel Fixed-Parameter Algorithms via Color Coding.
CoRR
Max Bannach, Christoph Stockhusen, Till Tantau
2015 B conf
Fast Parallel Fixed-parameter Algorithms via Color Coding.
IPEC
Max Bannach, Christoph Stockhusen, Till Tantau
2015 J jnl
On the Space and Circuit Complexity of Parameterized Problems: Classes and Completeness.
Algorithmica
Michael Elberfeld, Christoph Stockhusen, Till Tantau
2014 J jnl
Existential Second-Order Logic Over Graphs: A Complete Complexity-Theoretic Classification.
CoRR
Till Tantau
2013 B conf
Completeness Results for Parameterized Space Classes.
IPEC
Christoph Stockhusen, Till Tantau
2013 J jnl
Completeness Results for Parameterized Space Classes.
CoRR
Christoph Stockhusen, Till Tantau
2013 J jnl
Graph Drawing in TikZ.
J. Graph Algorithms Appl.
Till Tantau
2012 A conf
Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth.
STACS
Michael Elberfeld, Andreas Jakoby, Till Tantau
2012 A conf
Graph Drawing in TikZ.
GD
Till Tantau
2012 J jnl
Influence of tree topology restrictions on the complexity of haplotyping with missing data.
Theor. Comput. Sci.
Michael Elberfeld, Ilka Schnoor, Till Tantau
2012 B conf
On the Space Complexity of Parameterized Problems.
IPEC
Michael Elberfeld, Christoph Stockhusen, Till Tantau
2012 J jnl
On the Space Complexity of Parameterized Problems.
Electron. Colloquium Comput. Complex.
Michael Elberfeld, Christoph Stockhusen, Till Tantau
2012 J jnl
Phylogeny- and parsimony-based haplotype inference with constraints.
Inf. Comput.
Michael Elberfeld, Till Tantau
2012 J jnl
Smoothed analysis of left-to-right maxima with applications.
ACM Trans. Algorithms
Valentina Damerow, Bodo Manthey, Friedhelm Meyer auf der Heide, Harald Räcke, Christian Scheideler, Christian Sohler, Till Tantau
2012 J jnl
Where First-Order and Monadic Second-Order Logic Coincide
CoRR
Michael Elberfeld, Martin Grohe, Till Tantau
2012 A* conf
Where First-Order and Monadic Second-Order Logic Coincide.
LICS
Michael Elberfeld, Martin Grohe, Till Tantau
2011 J jnl
Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth.
Electron. Colloquium Comput. Complex.
Michael Elberfeld, Andreas Jakoby, Till Tantau
2011 — ch.
The One-Time Pad Algorithm - The Simplest and Most Secure Way to Keep Secrets.
Algorithms Unplugged
Till Tantau
2010 A* conf
Logspace Versions of the Theorems of Bodlaender and Courcelle.
FOCS
Michael Elberfeld, Andreas Jakoby, Till Tantau
2010 J jnl
Logspace Versions of the Theorems of Bodlaender and Courcelle.
Electron. Colloquium Comput. Complex.
Michael Elberfeld, Andreas Jakoby, Till Tantau
2010 J jnl
On the complexity of kings.
Theor. Comput. Sci.
Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe
2010 B conf
Phylogeny- and Parsimony-Based Haplotype Inference with Constraints.
CPM
Michael Elberfeld, Till Tantau
2009 C conf
Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data.
TAMC
Michael Elberfeld, Ilka Schnoor, Till Tantau
2009 J jnl
On the complexity of SNP block partitioning under the perfect phylogeny model.
Discret. Math.
Jens Gramm, Tzvika Hartman, Till Nierhoff, Roded Sharan, Till Tantau
2008 B conf
Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems.
MFCS
Michael Elberfeld, Till Tantau
2008 — ch.
Der One-Time-Pad-Algorithmus: Der einfachste und sicherste Verschlüsselungsalgorithmus.
Taschenbuch der Algorithmen
Till Tantau
2008 J jnl
Fixed-Parameter Algorithms in Phylogenetics.
Comput. J.
Jens Gramm, Arfst Nickelsen, Till Tantau
2008 J jnl
Generalizations of the Hartmanis-Immerman-Sewelson Theorem and Applications to Infinite Subsets of P-Selective Sets.
Electron. Colloquium Comput. Complex.
Till Tantau
2008 B conf
Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise.
MFCS
Bodo Manthey, Till Tantau
2007 J jnl
Haplotyping with missing data via perfect path phylogenies.
Discret. Appl. Math.
Jens Gramm, Till Nierhoff, Roded Sharan, Till Tantau
2007 — conf
Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs.
FSTTCS
Andreas Jakoby, Till Tantau
2007 J jnl
Logspace Optimization Problems and Their Approximability Properties.
Theory Comput. Syst.
Till Tantau
2007 B conf
On the Complexity of Kings.
FCT
Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe
2007 — conf
Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise.
Probabilistic Methods in the Design and Analysis of Algorithms
Bodo Manthey, Till Tantau
2007 J jnl
Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise.
Electron. Colloquium Comput. Complex.
Bodo Manthey, Till Tantau
2006 — conf
Computing Shortest Paths in Series-Parallel Graphs in Logarithmic Space.
Complexity of Boolean Functions
Andreas Jakoby, Till Tantau
2006 C conf
On the Complexity of SNP Block Partitioning Under the Perfect Phylogeny Model.
WABI
Jens Gramm, Tzvika Hartman, Till Nierhoff, Roded Sharan, Till Tantau
2006 — conf
Optimal Flow Distribution Among Multiple Channels with Unknown Capacities .
Essays in Memory of Shimon Even
Richard M. Karp, Till Nierhoff, Till Tantau
2006 J jnl
The Descriptive Complexity of the Reachability Problem As a Function of Different Graph Parameters.
Electron. Colloquium Comput. Complex.
Till Tantau
2005 J jnl
Context-free languages can be accepted with absolutely no space overhead.
Inf. Comput.
Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau
2005 B conf
Logspace Optimization Problems and Their Approximability Properties.
FCT
Till Tantau
2005 J jnl
Optimal flow distribution among multiple channels with unknown capacities.
Electron. Notes Discret. Math.
Richard M. Karp, Till Nierhoff, Till Tantau
2005 J jnl
The Complexity of Finding Paths in Graphs with Bounded Independence Number.
SIAM J. Comput.
Arfst Nickelsen, Till Tantau
2005 J jnl
Weak cardinality theorems.
J. Symb. Log.
Till Tantau
2004 A conf
A Logspace Approximation Scheme for the Shortest Path Problem for Graphs with Bounded Independence Number.
STACS
Till Tantau
2004 J jnl
Aggregates with Component Size One Characterize Polynomial Space
Electron. Colloquium Comput. Complex.
Arfst Nickelsen, Till Tantau, Lorenz Weizsäcker
2004 J jnl
Comparing Verboseness for Finite Automata and Turing Machines.
Theory Comput. Syst.
Till Tantau
2004 J jnl
On the reducibility of sets inside NP to sets with low information content.
J. Comput. Syst. Sci.
Mitsunori Ogihara, Till Tantau
2004 J jnl
Overhead-Free Computation, DCFLs, and CFLs
CoRR
Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau
2004 — conf
Perfect Path Phylogeny Haplotyping with Missing Data Is Fixed-Parameter Tractable.
IWPEC
Jens Gramm, Till Nierhoff, Till Tantau
2003 — ch.
Aufzählbarkeitsklassen von Turingmaschinen und endlichen Automaten.
Ausgezeichnete Informatikdissertationen
Till Tantau
2003 C conf
Computation with Absolutely No Space Overhead.
Developments in Language Theory
Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau
2003 J jnl
Logspace Optimisation Problems and their Approximation Properties
Electron. Colloquium Comput. Complex.
Till Tantau
2003 — book
On structural similarities of finite automata and Turing machine enumerability classes.
Till Tantau
2003 J jnl
Partial information classes.
SIGACT News
Arfst Nickelsen, Till Tantau
2003 J jnl
Query complexity of membership comparable sets.
Theor. Comput. Sci.
Till Tantau
2003 J jnl
Weak Cardinality Theorems for First-Order Logic
Electron. Colloquium Comput. Complex.
Till Tantau
2003 B conf
Weak Cardinality Theorems for First-Order Logic.
FCT
Till Tantau
2002 J jnl
A Note on the Power of Extra Queries to Membership Comparable Sets
Electron. Colloquium Comput. Complex.
Till Tantau
2002 A conf
Comparing Verboseness for Finite Automata and Turing Machines.
STACS
Till Tantau
2002 Misc conf
On Reachability in Graphs with Bounded Independence Number.
COCOON
Arfst Nickelsen, Till Tantau
2002 B conf
Towards a Cardinality Theorem for Finite Automata.
MFCS
Till Tantau
2001 J jnl
A Note on the Complexity of the Reachability Problem for Tournaments
Electron. Colloquium Comput. Complex.
Till Tantau
2001 B conf
Closure of Polynomial Time Partial Information Classes under Polynomial Time Reductions.
FCT
Arfst Nickelsen, Till Tantau
2000 J jnl
On the Power of Extra Queries to Selective Languages
Electron. Colloquium Comput. Complex.
Till Tantau
1999 — conf
Reflections in Opal - Meta Information in a Functional Programming Language.
IFL
Klaus Didrich, Wolfgang Grieskamp, Florian Schintke, Till Tantau, Baltasar Trancón y Widemann