default search action
Till Tantau
Person information
- affiliation: University of Lübeck, Germany
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [c44]Max Bannach, Florian Chudigiewitsch, Till Tantau:
On the Descriptive Complexity of Vertex Deletion Problems. MFCS 2024: 17:1-17:14 - [c43]Max Bannach, Florian Andreas Marwitz, Till Tantau:
Faster Graph Algorithms Through DAG Compression. STACS 2024: 8:1-8:18 - [i34]Max Bannach, Florian Chudigiewitsch, Till Tantau:
On the Descriptive Complexity of Vertex Deletion Problems. CoRR abs/2406.18299 (2024) - 2023
- [j24]Max Bannach
, Malte Skambath
On the Parallel Parameterized Complexity of MaxSAT Variants. J. Artif. Intell. Res. 78 (2023) - [c42]Max Bannach, Florian Chudigiewitsch, Till Tantau:
Existential Second-Order Logic over Graphs: Parameterized Complexity. IPEC 2023: 3:1-3:15 - [i33]Max Bannach, Florian Chudigiewitsch
Existential Second-Order Logic Over Graphs: Parameterized Complexity. CoRR abs/2310.01134 (2023) - [i32]Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau, Manaswi Paraashar:
Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111). Dagstuhl Reports 13(3): 17-31 (2023) - 2022
- [j23]Max Bannach, Zacharias Heinrich
Dynamic Kernels for Hitting Sets and Set Packing. Algorithmica 84(11): 3459-3488 (2022) - [c41]Till Tantau:
On the Satisfaction Probability of k-CNF Formulas. CCC 2022: 2:1-2:27 - [c40]Laurent Bulteau, Mark Jones, Rolf Niedermeier, Till Tantau:
An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions. CPM 2022: 6:1-6:11 - [c39]Max Bannach, Malte Skambath, Till Tantau:
On the Parallel Parameterized Complexity of MaxSAT Variants. SAT 2022: 19:1-19:19 - [i31]Till Tantau:
On the Satisfaction Probability of k-CNF Formulas. CoRR abs/2201.08895 (2022) - [i30]Max Bannach, Malte Skambath, Till Tantau:
On the Parallel Parameterized Complexity of MaxSAT Variants. CoRR abs/2206.01280 (2022) - 2021
- [j22]Max Bannach
On the Descriptive Complexity of Color Coding. Algorithms 14(3): 96 (2021) - [c38]Jonas Schmidt, Thomas Schwentick, Till Tantau, Nils Vortmeier, Thomas Zeume:
Work-sensitive Dynamic Complexity of Formal Languages. FoSSaCS 2021: 490-509 - [c37]Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau:
Dynamic Kernels for Hitting Sets and Set Packing. IPEC 2021: 7:1-7:18 - [c36]Till Tantau:
Informatik fürs Leben lernen. INFOS 2021: 25-38 - [i29]Jonas Schmidt, Thomas Schwentick, Till Tantau, Nils Vortmeier, Thomas Zeume:
Work-sensitive Dynamic Complexity of Formal Languages. CoRR abs/2101.08735 (2021) - [i28]Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau:
Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121). Dagstuhl Reports 11(2): 1-16 (2021) - 2020
- [j21]Max Bannach, Till Tantau
Computing Hitting Set Kernels By AC0-Circuits. Theory Comput. Syst. 64(3): 374-399 (2020) - [c35]Max Bannach, Malte Skambath, Till Tantau:
Kernelizing the Hitting Set Problem in Linear Sequential and Constant Parallel Time. SWAT 2020: 9:1-9:16
2010 – 2019
- 2019
- [c34]Max Bannach, Till Tantau:
On the Descriptive Complexity of Color Coding. STACS 2019: 11:1-11:16 - [c33]Max Bannach, Malte Skambath, Till Tantau:
Towards Work-Efficient Parallel Parameterized Algorithms. WALCOM 2019: 341-353 - [i27]Max Bannach, Till Tantau:
On the Descriptive Complexity of Color Coding. CoRR abs/1901.03364 (2019) - [i26]Max Bannach, Malte Skambath, Till Tantau:
Towards Work-Efficient Parallel Parameterized Algorithms. CoRR abs/1902.07660 (2019) - [i25]Anna Gál, Rahul Santhanam, Till Tantau:
Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121). Dagstuhl Reports 9(3): 64-82 (2019) - [i24]Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau:
Dynamic Kernels for Hitting Sets and Set Packing. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [c32]Christian Herzog né Hoffmann, Till Tantau, Philipp Rostalski:
Study Program "Robotics and Autonomous Systems" at the University of Lübeck. EWME 2018: 17-19 - [c31]Max Bannach, Till Tantau:
Computing Kernels in Parallel: Lower and Upper Bounds. IPEC 2018: 13:1-13:14 - [c30]Max Bannach, Till Tantau:
Computing Hitting Set Kernels By AC^0-Circuits. STACS 2018: 9:1-9:14 - [i23]Max Bannach, Till Tantau:
Computing Hitting Set Kernels By AC^0-Circuits. CoRR abs/1801.00716 (2018) - [i22]Max Bannach, Till Tantau:
Computing Kernels in Parallel: Lower and Upper Bounds. CoRR abs/1807.03604 (2018) - 2017
- [c29]Till Tantau:
Applications of Algorithmic Metatheorems to Space Complexity and Parallelism (Invited Talk). STACS 2017: 4:1-4:4 - [i21]Anna Gál, Michal Koucký, Oded Regev, Till Tantau:
Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121). Dagstuhl Reports 7(3): 45-69 (2017) - 2016
- [j20]Till Tantau:
A Gentle Introduction to Applications of Algorithmic Metatheorems for Space and Circuit Classes. Algorithms 9(3): 44 (2016) - [j19]Michael Elberfeld, Martin Grohe, Till Tantau:
Where First-Order and Monadic Second-Order Logic Coincide. ACM Trans. Comput. Log. 17(4): 25 (2016) - [c28]Malte Skambath, Till Tantau:
Offline Drawing of Dynamic Trees: Algorithmics and Document Integration. GD 2016: 572-586 - [c27]Max Bannach, Till Tantau:
Parallel Multivariate Meta-Theorems. IPEC 2016: 4:1-4:17 - [i20]Malte Skambath, Till Tantau:
Offline Drawing of Dynamic Trees: Algorithmics and Document Integration. CoRR abs/1608.08385 (2016) - 2015
- [j18]Michael Elberfeld, Christoph Stockhusen, Till Tantau:
On the Space and Circuit Complexity of Parameterized Problems: Classes and Completeness. Algorithmica 71(3): 661-701 (2015) - [c26]Max Bannach, Christoph Stockhusen, Till Tantau:
Fast Parallel Fixed-parameter Algorithms via Color Coding. IPEC 2015: 224-235 - [c25]Till Tantau:
Existential Second-order Logic over Graphs: A Complete Complexity-theoretic Classification. STACS 2015: 703-715 - [i19]Max Bannach, Christoph Stockhusen, Till Tantau:
Fast Parallel Fixed-Parameter Algorithms via Color Coding. CoRR abs/1509.06984 (2015) - 2014
- [i18]Till Tantau:
Existential Second-Order Logic Over Graphs: A Complete Complexity-Theoretic Classification. CoRR abs/1412.6396 (2014) - 2013
- [j17]Till Tantau:
Graph Drawing in TikZ. J. Graph Algorithms Appl. 17(4): 495-513 (2013) - [c24]Christoph Stockhusen, Till Tantau:
Completeness Results for Parameterized Space Classes. IPEC 2013: 335-347 - [i17]Christoph Stockhusen, Till Tantau:
Completeness Results for Parameterized Space Classes. CoRR abs/1308.2892 (2013) - 2012
- [j16]Michael Elberfeld, Till Tantau:
Phylogeny- and parsimony-based haplotype inference with constraints. Inf. Comput. 213: 33-47 (2012) - [j15]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): 30:1-30:28 (2012) - [j14]Michael Elberfeld, Ilka Schnoor, Till Tantau:
Influence of tree topology restrictions on the complexity of haplotyping with missing data. Theor. Comput. Sci. 432: 38-51 (2012) - [c23]Till Tantau:
Graph Drawing in TikZ. GD 2012: 517-528 - [c22]Michael Elberfeld, Christoph Stockhusen, Till Tantau:
On the Space Complexity of Parameterized Problems. IPEC 2012: 206-217 - [c21]Michael Elberfeld, Martin Grohe
Where First-Order and Monadic Second-Order Logic Coincide. LICS 2012: 265-274 - [c20]Michael Elberfeld, Andreas Jakoby, Till Tantau:
Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth. STACS 2012: 66-77 - [i16]Michael Elberfeld, Martin Grohe, Till Tantau:
Where First-Order and Monadic Second-Order Logic Coincide. CoRR abs/1204.6291 (2012) - [i15]Michael Elberfeld, Christoph Stockhusen, Till Tantau:
On the Space Complexity of Parameterized Problems. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [p3]Till Tantau:
The One-Time Pad Algorithm - The Simplest and Most Secure Way to Keep Secrets. Algorithms Unplugged 2011: 141-146 - [i14]Michael Elberfeld, Andreas Jakoby, Till Tantau:
Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j13]Edith Hemaspaandra, Lane A. Hemaspaandra
On the complexity of kings. Theor. Comput. Sci. 411(4-5): 783-798 (2010) - [c19]Michael Elberfeld, Till Tantau:
Phylogeny- and Parsimony-Based Haplotype Inference with Constraints. CPM 2010: 177-189 - [c18]Michael Elberfeld, Andreas Jakoby, Till Tantau:
Logspace Versions of the Theorems of Bodlaender and Courcelle. FOCS 2010: 143-152 - [i13]Michael Elberfeld, Andreas Jakoby, Till Tantau:
Logspace Versions of the Theorems of Bodlaender and Courcelle. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j12]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): 5610-5617 (2009) - [c17]Michael Elberfeld, Ilka Schnoor, Till Tantau:
Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data. TAMC 2009: 201-210 - 2008
- [j11]Jens Gramm, Arfst Nickelsen, Till Tantau:
Fixed-Parameter Algorithms in Phylogenetics. Comput. J. 51(1): 79-101 (2008) - [c16]Michael Elberfeld, Till Tantau:
Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems. MFCS 2008: 299-310 - [c15]Bodo Manthey, Till Tantau:
Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise. MFCS 2008: 467-478 - [p2]Till Tantau:
Der One-Time-Pad-Algorithmus: Der einfachste und sicherste Verschlüsselungsalgorithmus. Taschenbuch der Algorithmen 2008: 149-155 - [i12]Till Tantau:
Generalizations of the Hartmanis-Immerman-Sewelson Theorem and Applications to Infinite Subsets of P-Selective Sets. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [j10]Jens Gramm, Till Nierhoff, Roded Sharan, Till Tantau:
Haplotyping with missing data via perfect path phylogenies. Discret. Appl. Math. 155(6-7): 788-805 (2007) - [j9]Till Tantau:
Logspace Optimization Problems and Their Approximability Properties. Theory Comput. Syst. 41(2): 327-350 (2007) - [c14]Edith Hemaspaandra, Lane A. Hemaspaandra
On the Complexity of Kings. FCT 2007: 328-340 - [c13]Andreas Jakoby, Till Tantau:
Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs. FSTTCS 2007: 216-227 - [i11]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 - [i10]Bodo Manthey, Till Tantau:
Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [c12]Richard M. Karp, Till Nierhoff, Till Tantau:
Optimal Flow Distribution Among Multiple Channels with Unknown Capacities . Essays in Memory of Shimon Even 2006: 111-128 - [c11]Jens Gramm, Tzvika Hartman, Till Nierhoff, Roded Sharan, Till Tantau:
On the Complexity of SNP Block Partitioning Under the Perfect Phylogeny Model. WABI 2006: 92-102 - [i9]Andreas Jakoby, Till Tantau:
Computing Shortest Paths in Series-Parallel Graphs in Logarithmic Space. Complexity of Boolean Functions 2006 - [i8]Till Tantau:
The Descriptive Complexity of the Reachability Problem As a Function of Different Graph Parameters. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [j8]Richard M. Karp, Till Nierhoff, Till Tantau:
Optimal flow distribution among multiple channels with unknown capacities. Electron. Notes Discret. Math. 19: 225-231 (2005) - [j7]Lane A. Hemaspaandra
Context-free languages can be accepted with absolutely no space overhead. Inf. Comput. 203(2): 163-180 (2005) - [j6]Till Tantau:
Weak cardinality theorems. J. Symb. Log. 70(3): 861-878 (2005) - [j5]Arfst Nickelsen, Till Tantau:
The Complexity of Finding Paths in Graphs with Bounded Independence Number. SIAM J. Comput. 34(5): 1176-1195 (2005) - [c10]Till Tantau:
Logspace Optimization Problems and Their Approximability Properties. FCT 2005: 103-114 - 2004
- [j4]Mitsunori Ogihara
On the reducibility of sets inside NP to sets with low information content. J. Comput. Syst. Sci. 69(4): 499-524 (2004) - [j3]Till Tantau:
Comparing Verboseness for Finite Automata and Turing Machines. Theory Comput. Syst. 37(1): 95-109 (2004) - [c9]Jens Gramm, Till Nierhoff, Till Tantau:
Perfect Path Phylogeny Haplotyping with Missing Data Is Fixed-Parameter Tractable. IWPEC 2004: 174-186 - [c8]Till Tantau:
A Logspace Approximation Scheme for the Shortest Path Problem for Graphs with Bounded Independence Number. STACS 2004: 326-337 - [i7]Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau:
Overhead-Free Computation, DCFLs, and CFLs. CoRR cs.CC/0410035 (2004) - [i6]Arfst Nickelsen, Till Tantau, Lorenz Weizsäcker:
Aggregates with Component Size One Characterize Polynomial Space. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [b1]Till Tantau:
On structural similarities of finite automata and Turing machine enumerability classes. Technical University of Berlin, Germany, Wissenschaft & Technik Verlag 2003, ISBN 978-3-89685-200-7, pp. 1-170 - [j2]Arfst Nickelsen, Till Tantau:
Partial information classes. SIGACT News 34(1): 32-46 (2003) - [j1]Till Tantau:
Query complexity of membership comparable sets. Theor. Comput. Sci. 302(1-3): 467-474 (2003) - [c7]Lane A. Hemaspaandra
Computation with Absolutely No Space Overhead. Developments in Language Theory 2003: 325-336 - [c6]Till Tantau:
Weak Cardinality Theorems for First-Order Logic. FCT 2003: 400-411 - [p1]Till Tantau:
Aufzählbarkeitsklassen von Turingmaschinen und endlichen Automaten. Ausgezeichnete Informatikdissertationen 2003: 189-198 - [i5]Till Tantau:
Weak Cardinality Theorems for First-Order Logic. Electron. Colloquium Comput. Complex. TR03 (2003) - [i4]Till Tantau:
Logspace Optimisation Problems and their Approximation Properties. Electron. Colloquium Comput. Complex. TR03 (2003) - 2002
- [c5]Arfst Nickelsen, Till Tantau:
On Reachability in Graphs with Bounded Independence Number. COCOON 2002: 554-563 - [c4]Till Tantau:
Towards a Cardinality Theorem for Finite Automata. MFCS 2002: 625-636 - [c3]Till Tantau:
Comparing Verboseness for Finite Automata and Turing Machines. STACS 2002: 465-476 - [i3]Till Tantau:
A Note on the Power of Extra Queries to Membership Comparable Sets. Electron. Colloquium Comput. Complex. TR02 (2002) - 2001
- [c2]Arfst Nickelsen, Till Tantau:
Closure of Polynomial Time Partial Information Classes under Polynomial Time Reductions. FCT 2001: 299-310 - [i2]Till Tantau:
A Note on the Complexity of the Reachability Problem for Tournaments. Electron. Colloquium Comput. Complex. TR01 (2001) - 2000
- [i1]Till Tantau:
On the Power of Extra Queries to Selective Languages. Electron. Colloquium Comput. Complex. TR00 (2000)
1990 – 1999
- 1999
- [c1]Klaus Didrich, Wolfgang Grieskamp, Florian Schintke, Till Tantau, Baltasar Trancón y Widemann
Reflections in Opal - Meta Information in a Functional Programming Language. IFL 1999: 149-164
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-15 20:44 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: