Till Tantau

ORCID

Publication Activity (10 Years)

Years Active: 1999-2024
Publications (10 Years): 39

Top Venues

Publications

Max Bannach, Florian Andreas Marwitz, Till Tantau
Faster Graph Algorithms Through DAG Compression. STACS (2024)
Max Bannach, Florian Chudigiewitsch, Till Tantau
On the Descriptive Complexity of Vertex Deletion Problems. MFCS (2024)
Max Bannach, Florian Chudigiewitsch, Till Tantau
On the Descriptive Complexity of Vertex Deletion Problems. CoRR (2024)
Max Bannach, Florian Chudigiewitsch, Till Tantau
Existential Second-Order Logic over Graphs: Parameterized Complexity. IPEC (2023)
Max Bannach, Malte Skambath, Till Tantau
On the Parallel Parameterized Complexity of MaxSAT Variants. J. Artif. Intell. Res. 78 (2023)
Max Bannach, Florian Chudigiewitsch, Till Tantau
Existential Second-Order Logic Over Graphs: Parameterized Complexity. CoRR (2023)
Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau, Manaswi Paraashar
Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111). Dagstuhl Reports 13 (3) (2023)
Till Tantau
On the Satisfaction Probability of k-CNF Formulas. CoRR (2022)
Laurent Bulteau, Mark Jones, Rolf Niedermeier, Till Tantau
An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions. CPM (2022)
Max Bannach, Malte Skambath, Till Tantau
On the Parallel Parameterized Complexity of MaxSAT Variants. SAT (2022)
Till Tantau
On the Satisfaction Probability of k-CNF Formulas. CCC (2022)
Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau
Dynamic Kernels for Hitting Sets and Set Packing. Algorithmica 84 (11) (2022)
Max Bannach, Malte Skambath, Till Tantau
On the Parallel Parameterized Complexity of MaxSAT Variants. CoRR (2022)
Max Bannach, Till Tantau
On the Descriptive Complexity of Color Coding. Algorithms 14 (3) (2021)
Jonas Schmidt, Thomas Schwentick, Till Tantau, Nils Vortmeier, Thomas Zeume
Work-sensitive Dynamic Complexity of Formal Languages. CoRR (2021)
Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau
Dynamic Kernels for Hitting Sets and Set Packing. IPEC (2021)
Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau
Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121). Dagstuhl Reports 11 (2) (2021)
Till Tantau
Informatik fürs Leben lernen. INFOS (2021)
Jonas Schmidt, Thomas Schwentick, Till Tantau, Nils Vortmeier, Thomas Zeume
Work-sensitive Dynamic Complexity of Formal Languages. FoSSaCS (2021)
Max Bannach, Till Tantau
-Circuits. Theory Comput. Syst. 64 (3) (2020)
Max Bannach, Malte Skambath, Till Tantau
Kernelizing the Hitting Set Problem in Linear Sequential and Constant Parallel Time. SWAT (2020)
Max Bannach, Malte Skambath, Till Tantau
Towards Work-Efficient Parallel Parameterized Algorithms. CoRR (2019)
Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau
Dynamic Kernels for Hitting Sets and Set Packing. Electron. Colloquium Comput. Complex. 26 (2019)
Max Bannach, Till Tantau
On the Descriptive Complexity of Color Coding. STACS (2019)
Max Bannach, Malte Skambath, Till Tantau
Towards Work-Efficient Parallel Parameterized Algorithms. WALCOM (2019)
Anna Gál, Rahul Santhanam, Till Tantau
Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121). Dagstuhl Reports 9 (3) (2019)
Max Bannach, Till Tantau
On the Descriptive Complexity of Color Coding. CoRR (2019)
Max Bannach, Till Tantau
Computing Kernels in Parallel: Lower and Upper Bounds. IPEC (2018)
Christian Herzog né Hoffmann, Till Tantau, Philipp Rostalski
Study Program "Robotics and Autonomous Systems" at the University of Lübeck. EWME (2018)
Max Bannach, Till Tantau
Computing Hitting Set Kernels By AC^0-Circuits. CoRR (2018)
Max Bannach, Till Tantau
Computing Hitting Set Kernels By AC^0-Circuits. STACS (2018)
Max Bannach, Till Tantau
Computing Kernels in Parallel: Lower and Upper Bounds. CoRR (2018)
Anna Gál, Michal Koucký, Oded Regev, Till Tantau
Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121). Dagstuhl Reports 7 (3) (2017)
Till Tantau
Applications of Algorithmic Metatheorems to Space Complexity and Parallelism (Invited Talk). STACS (2017)
Till Tantau
A Gentle Introduction to Applications of Algorithmic Metatheorems for Space and Circuit Classes. Algorithms 9 (3) (2016)
Max Bannach, Till Tantau
Parallel Multivariate Meta-Theorems. IPEC (2016)
Malte Skambath, Till Tantau
Offline Drawing of Dynamic Trees: Algorithmics and Document Integration. CoRR (2016)
Malte Skambath, Till Tantau
Offline Drawing of Dynamic Trees: Algorithmics and Document Integration. Graph Drawing (2016)
Michael Elberfeld, Martin Grohe, Till Tantau
Where First-Order and Monadic Second-Order Logic Coincide. ACM Trans. Comput. Log. 17 (4) (2016)
Michael Elberfeld, Christoph Stockhusen, Till Tantau
On the Space and Circuit Complexity of Parameterized Problems: Classes and Completeness. Algorithmica 71 (3) (2015)
Till Tantau
Existential Second-order Logic over Graphs: A Complete Complexity-theoretic Classification. STACS (2015)
Max Bannach, Christoph Stockhusen, Till Tantau
Fast Parallel Fixed-parameter Algorithms via Color Coding. IPEC (2015)
Max Bannach, Christoph Stockhusen, Till Tantau
Fast Parallel Fixed-Parameter Algorithms via Color Coding. CoRR (2015)
Till Tantau
Existential Second-Order Logic Over Graphs: A Complete Complexity-Theoretic Classification. CoRR (2014)
Christoph Stockhusen, Till Tantau
Completeness Results for Parameterized Space Classes. CoRR (2013)
Till Tantau
Graph Drawing in TikZ. J. Graph Algorithms Appl. 17 (4) (2013)
Christoph Stockhusen, Till Tantau
Completeness Results for Parameterized Space Classes. IPEC (2013)
Michael Elberfeld, Till Tantau
Phylogeny- and parsimony-based haplotype inference with constraints. Inf. Comput. 213 (2012)
Michael Elberfeld, Christoph Stockhusen, Till Tantau
On the Space Complexity of Parameterized Problems. IPEC (2012)
Michael Elberfeld, Ilka Schnoor, Till Tantau
Influence of tree topology restrictions on the complexity of haplotyping with missing data. Theor. Comput. Sci. 432 (2012)
Till Tantau
Graph Drawing in TikZ. Graph Drawing (2012)
Michael Elberfeld, Andreas Jakoby, Till Tantau
Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth. STACS (2012)
Michael Elberfeld, Christoph Stockhusen, Till Tantau
On the Space Complexity of Parameterized Problems. Electron. Colloquium Comput. Complex. 19 (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 Trans. Algorithms 8 (3) (2012)
Michael Elberfeld, Martin Grohe, Till Tantau
Where First-Order and Monadic Second-Order Logic Coincide CoRR (2012)
Michael Elberfeld, Martin Grohe, Till Tantau
Where First-Order and Monadic Second-Order Logic Coincide. LICS (2012)
Michael Elberfeld, Andreas Jakoby, Till Tantau
Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth. Electron. Colloquium Comput. Complex. 18 (2011)
Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe
On the complexity of kings. Theor. Comput. Sci. 411 (4-5) (2010)
Michael Elberfeld, Andreas Jakoby, Till Tantau
Logspace Versions of the Theorems of Bodlaender and Courcelle. Electron. Colloquium Comput. Complex. 17 (2010)
Michael Elberfeld, Andreas Jakoby, Till Tantau
Logspace Versions of the Theorems of Bodlaender and Courcelle. FOCS (2010)
Michael Elberfeld, Till Tantau
Phylogeny- and Parsimony-Based Haplotype Inference with Constraints. CPM (2010)
Jens Gramm, Tzvika Hartman, Till Nierhoff, Roded Sharan, Till Tantau
On the complexity of SNP block partitioning under the perfect phylogeny model. Discret. Math. 309 (18) (2009)
Michael Elberfeld, Ilka Schnoor, Till Tantau
Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data. TAMC (2009)
Till Tantau
Generalizations of the Hartmanis-Immerman-Sewelson Theorem and Applications to Infinite Subsets of P-Selective Sets. Electron. Colloquium Comput. Complex. 15 (027) (2008)
Bodo Manthey, Till Tantau
Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise. MFCS (2008)
Michael Elberfeld, Till Tantau
Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems. MFCS (2008)
Jens Gramm, Arfst Nickelsen, Till Tantau
Fixed-Parameter Algorithms in Phylogenetics. Comput. J. 51 (1) (2008)
Bodo Manthey, Till Tantau
Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise. Probabilistic Methods in the Design and Analysis of Algorithms (2007)
Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe
On the Complexity of Kings. FCT (2007)
Jens Gramm, Till Nierhoff, Roded Sharan, Till Tantau
Haplotyping with missing data via perfect path phylogenies. Discret. Appl. Math. 155 (6-7) (2007)
Till Tantau
Logspace Optimization Problems and Their Approximability Properties. Theory Comput. Syst. 41 (2) (2007)
Bodo Manthey, Till Tantau
Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise. Electron. Colloquium Comput. Complex. 14 (039) (2007)
Andreas Jakoby, Till Tantau
Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs. FSTTCS (2007)
Andreas Jakoby, Till Tantau
Computing Shortest Paths in Series-Parallel Graphs in Logarithmic Space. Complexity of Boolean Functions (2006)
Till Tantau
The Descriptive Complexity of the Reachability Problem As a Function of Different Graph Parameters. Electron. Colloquium Comput. Complex. 13 (035) (2006)
Jens Gramm, Tzvika Hartman, Till Nierhoff, Roded Sharan, Till Tantau
On the Complexity of SNP Block Partitioning Under the Perfect Phylogeny Model. WABI (2006)
Richard M. Karp, Till Nierhoff, Till Tantau
Optimal Flow Distribution Among Multiple Channels with Unknown Capacities . Essays in Memory of Shimon Even (2006)
Arfst Nickelsen, Till Tantau
The Complexity of Finding Paths in Graphs with Bounded Independence Number. SIAM J. Comput. 34 (5) (2005)
Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau
Context-free languages can be accepted with absolutely no space overhead. Inf. Comput. 203 (2) (2005)
Till Tantau
Logspace Optimization Problems and Their Approximability Properties. FCT (2005)
Richard M. Karp, Till Nierhoff, Till Tantau
Optimal flow distribution among multiple channels with unknown capacities. Electron. Notes Discret. Math. 19 (2005)
Till Tantau
Weak cardinality theorems. J. Symb. Log. 70 (3) (2005)
Arfst Nickelsen, Till Tantau, Lorenz Weizsäcker
Aggregates with Component Size One Characterize Polynomial Space Electron. Colloquium Comput. Complex. (028) (2004)
Mitsunori Ogihara, Till Tantau
On the reducibility of sets inside NP to sets with low information content. J. Comput. Syst. Sci. 69 (4) (2004)
Till Tantau
Comparing Verboseness for Finite Automata and Turing Machines. Theory Comput. Syst. 37 (1) (2004)
Jens Gramm, Till Nierhoff, Till Tantau
Perfect Path Phylogeny Haplotyping with Missing Data Is Fixed-Parameter Tractable. IWPEC (2004)
Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau
Overhead-Free Computation, DCFLs, and CFLs CoRR (2004)
Till Tantau
A Logspace Approximation Scheme for the Shortest Path Problem for Graphs with Bounded Independence Number. STACS (2004)
Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau
Computation with Absolutely No Space Overhead. Developments in Language Theory (2003)
Till Tantau
Query complexity of membership comparable sets. Theor. Comput. Sci. 302 (1-3) (2003)
Till Tantau
Aufzählbarkeitsklassen von Turingmaschinen und endlichen Automaten. Ausgezeichnete Informatikdissertationen (2003)
Till Tantau
Weak Cardinality Theorems for First-Order Logic. FCT (2003)
Till Tantau
Logspace Optimisation Problems and their Approximation Properties Electron. Colloquium Comput. Complex. (077) (2003)
Till Tantau
Weak Cardinality Theorems for First-Order Logic Electron. Colloquium Comput. Complex. 10 (024) (2003)
Arfst Nickelsen, Till Tantau
Partial information classes. SIGACT News 34 (1) (2003)
Till Tantau
Comparing Verboseness for Finite Automata and Turing Machines. STACS (2002)
Arfst Nickelsen, Till Tantau
On Reachability in Graphs with Bounded Independence Number. COCOON (2002)
Till Tantau
Towards a Cardinality Theorem for Finite Automata. MFCS (2002)
Till Tantau
A Note on the Power of Extra Queries to Membership Comparable Sets Electron. Colloquium Comput. Complex. (004) (2002)
Arfst Nickelsen, Till Tantau
Closure of Polynomial Time Partial Information Classes under Polynomial Time Reductions. FCT (2001)

Till Tantau.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Till Tantau