Till Tantau

Orcid: 0000-0002-3946-8028

Affiliations:
  • University of Lübeck, Germany


According to our database1, Till Tantau authored at least 73 papers between 1999 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Faster Graph Algorithms Through DAG Compression.
Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

On the Descriptive Complexity of Vertex Deletion Problems.
Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024

2023
Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111).
Dagstuhl Reports, March, 2023

On the Parallel Parameterized Complexity of MaxSAT Variants.
J. Artif. Intell. Res., 2023

Existential Second-Order Logic over Graphs: Parameterized Complexity.
Proceedings of the 18th International Symposium on Parameterized and Exact Computation, 2023

2022
An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions.
Proceedings of the 33rd Annual Symposium on Combinatorial Pattern Matching, 2022

On the Satisfaction Probability of k-CNF Formulas.
Proceedings of the 37th Computational Complexity Conference, 2022

2021
Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121).
Dagstuhl Reports, 2021

On the Descriptive Complexity of Color Coding.
Algorithms, 2021

Informatik fürs Leben lernen.
Proceedings of the 19. GI-Fachtagung Informatik und Schule, 2021

Work-sensitive Dynamic Complexity of Formal Languages.
Proceedings of the Foundations of Software Science and Computation Structures, 2021

2020
Computing Hitting Set Kernels By AC<sup>0</sup>-Circuits.
Theory Comput. Syst., 2020

Kernelizing the Hitting Set Problem in Linear Sequential and Constant Parallel Time.
Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory, 2020

2019
Dynamic Kernels for Hitting Sets and Set Packing.
Electron. Colloquium Comput. Complex., 2019

Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121).
Dagstuhl Reports, 2019

Towards Work-Efficient Parallel Parameterized Algorithms.
Proceedings of the WALCOM: Algorithms and Computation - 13th International Conference, 2019

2018
Computing Hitting Set Kernels By AC^0-Circuits.
Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

Computing Kernels in Parallel: Lower and Upper Bounds.
Proceedings of the 13th International Symposium on Parameterized and Exact Computation, 2018

Study Program "Robotics and Autonomous Systems" at the University of Lübeck.
Proceedings of the 12th European Workshop on Microelectronics Education, 2018

2017
Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121).
Dagstuhl Reports, 2017

Applications of Algorithmic Metatheorems to Space Complexity and Parallelism (Invited Talk).
Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

2016
Where First-Order and Monadic Second-Order Logic Coincide.
ACM Trans. Comput. Log., 2016

A Gentle Introduction to Applications of Algorithmic Metatheorems for Space and Circuit Classes.
Algorithms, 2016

Parallel Multivariate Meta-Theorems.
Proceedings of the 11th International Symposium on Parameterized and Exact Computation, 2016

Offline Drawing of Dynamic Trees: Algorithmics and Document Integration.
Proceedings of the Graph Drawing and Network Visualization - 24th International Symposium, 2016

2015
On the Space and Circuit Complexity of Parameterized Problems: Classes and Completeness.
Algorithmica, 2015

Existential Second-order Logic over Graphs: A Complete Complexity-theoretic Classification.
Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Fast Parallel Fixed-parameter Algorithms via Color Coding.
Proceedings of the 10th International Symposium on Parameterized and Exact Computation, 2015

2013
Graph Drawing in TikZ.
J. Graph Algorithms Appl., 2013

Completeness Results for Parameterized Space Classes.
Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

2012
Influence of tree topology restrictions on the complexity of haplotyping with missing data.
Theor. Comput. Sci., 2012

Smoothed analysis of left-to-right maxima with applications.
ACM Trans. Algorithms, 2012

Phylogeny- and parsimony-based haplotype inference with constraints.
Inf. Comput., 2012

On the Space Complexity of Parameterized Problems.
Electron. Colloquium Comput. Complex., 2012

2011
Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth.
Electron. Colloquium Comput. Complex., 2011

The One-Time Pad Algorithm - The Simplest and Most Secure Way to Keep Secrets.
Proceedings of the Algorithms Unplugged, 2011

2010
On the complexity of kings.
Theor. Comput. Sci., 2010

Logspace Versions of the Theorems of Bodlaender and Courcelle.
Electron. Colloquium Comput. Complex., 2010

2009
On the complexity of SNP block partitioning under the perfect phylogeny model.
Discret. Math., 2009

2008
Der One-Time-Pad-Algorithmus: Der einfachste und sicherste Verschlüsselungsalgorithmus.
Proceedings of the Taschenbuch der Algorithmen, 2008

Generalizations of the Hartmanis-Immerman-Sewelson Theorem and Applications to Infinite Subsets of P-Selective Sets.
Electron. Colloquium Comput. Complex., 2008

Fixed-Parameter Algorithms in Phylogenetics.
Comput. J., 2008

Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems.
Proceedings of the Mathematical Foundations of Computer Science 2008, 2008

2007
Logspace Optimization Problems and Their Approximability Properties.
Theory Comput. Syst., 2007

Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise.
Electron. Colloquium Comput. Complex., 2007

Haplotyping with missing data via perfect path phylogenies.
Discret. Appl. Math., 2007

Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs.
Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007

2006
The Descriptive Complexity of the Reachability Problem As a Function of Different Graph Parameters.
Electron. Colloquium Comput. Complex., 2006

Computing Shortest Paths in Series-Parallel Graphs in Logarithmic Space.
Proceedings of the Complexity of Boolean Functions, 12.03. - 17.03.2006, 2006

2005
The Complexity of Finding Paths in Graphs with Bounded Independence Number.
SIAM J. Comput., 2005

Weak cardinality theorems.
J. Symb. Log., 2005

Context-free languages can be accepted with absolutely no space overhead.
Inf. Comput., 2005

Optimal flow distribution among multiple channels with unknown capacities.
Electron. Notes Discret. Math., 2005

2004
Comparing Verboseness for Finite Automata and Turing Machines.
Theory Comput. Syst., 2004

On the reducibility of sets inside NP to sets with low information content.
J. Comput. Syst. Sci., 2004

Aggregates with Component Size One Characterize Polynomial Space
Electron. Colloquium Comput. Complex., 2004

Overhead-Free Computation, DCFLs, and CFLs
CoRR, 2004

A Logspace Approximation Scheme for the Shortest Path Problem for Graphs with Bounded Independence Number.
Proceedings of the STACS 2004, 2004

Perfect Path Phylogeny Haplotyping with Missing Data Is Fixed-Parameter Tractable.
Proceedings of the Parameterized and Exact Computation, First International Workshop, 2004

2003
Query complexity of membership comparable sets.
Theor. Comput. Sci., 2003

Partial information classes.
SIGACT News, 2003

Logspace Optimisation Problems and their Approximation Properties
Electron. Colloquium Comput. Complex., 2003

Weak Cardinality Theorems for First-Order Logic
Electron. Colloquium Comput. Complex., 2003

Aufzählbarkeitsklassen von Turingmaschinen und endlichen Automaten.
Proceedings of the Ausgezeichnete Informatikdissertationen 2003, 2003

Computation with Absolutely No Space Overhead.
Proceedings of the Developments in Language Theory, 7th International Conference, 2003

On structural similarities of finite automata and Turing machine enumerability classes.
Wissenschaft & Technik Verlag, ISBN: 978-3-89685-200-7, 2003

2002
A Note on the Power of Extra Queries to Membership Comparable Sets
Electron. Colloquium Comput. Complex., 2002

Towards a Cardinality Theorem for Finite Automata.
Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

On Reachability in Graphs with Bounded Independence Number.
Proceedings of the Computing and Combinatorics, 8th Annual International Conference, 2002

2001
A Note on the Complexity of the Reachability Problem for Tournaments
Electron. Colloquium Comput. Complex., 2001

Closure of Polynomial Time Partial Information Classes under Polynomial Time Reductions.
Proceedings of the Fundamentals of Computation Theory, 13th International Symposium, 2001

2000
On the Power of Extra Queries to Selective Languages
Electron. Colloquium Comput. Complex., 2000

1999
Reflections in Opal - Meta Information in a Functional Programming Language.
Proceedings of the Implementation of Functional Languages, 11th International Workshop, 1999


  Loading...