Published in: Dagstuhl Reports, Volume 13, Issue 3 (2023)
Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau, and Manaswi Paraashar. Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111). In Dagstuhl Reports, Volume 13, Issue 3, pp. 17-31, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@Article{gal_et_al:DagRep.13.3.17, author = {G\'{a}l, Anna and Mahajan, Meena and Santhanam, Rahul and Tantau, Till and Paraashar, Manaswi}, title = {{Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111)}}, pages = {17--31}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2023}, volume = {13}, number = {3}, editor = {G\'{a}l, Anna and Mahajan, Meena and Santhanam, Rahul and Tantau, Till and Paraashar, Manaswi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.3.17}, URN = {urn:nbn:de:0030-drops-192261}, doi = {10.4230/DagRep.13.3.17}, annote = {Keywords: circuit complexity, communication complexity, computational complexity, lower bounds, randomness} }
Published in: LIPIcs, Volume 236, 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022)
Max Bannach, Malte Skambath, and Till Tantau. On the Parallel Parameterized Complexity of MaxSAT Variants. In 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 236, pp. 19:1-19:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bannach_et_al:LIPIcs.SAT.2022.19, author = {Bannach, Max and Skambath, Malte and Tantau, Till}, title = {{On the Parallel Parameterized Complexity of MaxSAT Variants}}, booktitle = {25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022)}, pages = {19:1--19:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-242-6}, ISSN = {1868-8969}, year = {2022}, volume = {236}, editor = {Meel, Kuldeep S. and Strichman, Ofer}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2022.19}, URN = {urn:nbn:de:0030-drops-166934}, doi = {10.4230/LIPIcs.SAT.2022.19}, annote = {Keywords: max-sat, almost-sat, parallel algorithms, fixed-parameter tractability} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Till Tantau. On the Satisfaction Probability of k-CNF Formulas. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 2:1-2:27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{tantau:LIPIcs.CCC.2022.2, author = {Tantau, Till}, title = {{On the Satisfaction Probability of k-CNF Formulas}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {2:1--2:27}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.2}, URN = {urn:nbn:de:0030-drops-165648}, doi = {10.4230/LIPIcs.CCC.2022.2}, annote = {Keywords: Satisfaction probability, majority it\{k\}-sat, kernelization, well orderings, locality} }
Published in: LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)
Laurent Bulteau, Mark Jones, Rolf Niedermeier, and Till Tantau. An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions. In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 6:1-6:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bulteau_et_al:LIPIcs.CPM.2022.6, author = {Bulteau, Laurent and Jones, Mark and Niedermeier, Rolf and Tantau, Till}, title = {{An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions}}, booktitle = {33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)}, pages = {6:1--6:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-234-1}, ISSN = {1868-8969}, year = {2022}, volume = {223}, editor = {Bannai, Hideo and Holub, Jan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.6}, URN = {urn:nbn:de:0030-drops-161338}, doi = {10.4230/LIPIcs.CPM.2022.6}, annote = {Keywords: NP-hard string problems, multiple sequence alignment, center string, parameterized complexity, search tree algorithms, enumerative algorithms} }
Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, and Till Tantau. Dynamic Kernels for Hitting Sets and Set Packing. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 7:1-7:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{bannach_et_al:LIPIcs.IPEC.2021.7, author = {Bannach, Max and Heinrich, Zacharias and Reischuk, R\"{u}diger and Tantau, Till}, title = {{Dynamic Kernels for Hitting Sets and Set Packing}}, booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)}, pages = {7:1--7:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-216-7}, ISSN = {1868-8969}, year = {2021}, volume = {214}, editor = {Golovach, Petr A. and Zehavi, Meirav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.7}, URN = {urn:nbn:de:0030-drops-153900}, doi = {10.4230/LIPIcs.IPEC.2021.7}, annote = {Keywords: Kernelization, Dynamic Algorithms, Hitting Set, Set Packings} }
Published in: Dagstuhl Reports, Volume 11, Issue 2 (2021)
Anna Gál, Meena Mahajan, Rahul Santhanam, and Till Tantau. Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121). In Dagstuhl Reports, Volume 11, Issue 2, pp. 1-16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@Article{gal_et_al:DagRep.11.2.1, author = {G\'{a}l, Anna and Mahajan, Meena and Santhanam, Rahul and Tantau, Till}, title = {{Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121)}}, pages = {1--16}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2021}, volume = {11}, number = {2}, editor = {G\'{a}l, Anna and Mahajan, Meena and Santhanam, Rahul and Tantau, Till}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.2.1}, URN = {urn:nbn:de:0030-drops-146836}, doi = {10.4230/DagRep.11.2.1}, annote = {Keywords: circuit complexity, communication complexity, computational complexity, lower bounds, randomness} }
Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Max Bannach, Malte Skambath, and Till Tantau. Kernelizing the Hitting Set Problem in Linear Sequential and Constant Parallel Time. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 9:1-9:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{bannach_et_al:LIPIcs.SWAT.2020.9, author = {Bannach, Max and Skambath, Malte and Tantau, Till}, title = {{Kernelizing the Hitting Set Problem in Linear Sequential and Constant Parallel Time}}, booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)}, pages = {9:1--9:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-150-4}, ISSN = {1868-8969}, year = {2020}, volume = {162}, editor = {Albers, Susanne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.9}, URN = {urn:nbn:de:0030-drops-122566}, doi = {10.4230/LIPIcs.SWAT.2020.9}, annote = {Keywords: Kernelization, Approximation, Hitting Set, Constant-Depth Circuits} }
Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)
Jonas Schmidt, Thomas Schwentick, Nils Vortmeier, Thomas Zeume, and Ioannis Kokkinis. Dynamic Complexity Meets Parameterised Algorithms. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 36:1-36:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{schmidt_et_al:LIPIcs.CSL.2020.36, author = {Schmidt, Jonas and Schwentick, Thomas and Vortmeier, Nils and Zeume, Thomas and Kokkinis, Ioannis}, title = {{Dynamic Complexity Meets Parameterised Algorithms}}, booktitle = {28th EACSL Annual Conference on Computer Science Logic (CSL 2020)}, pages = {36:1--36:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-132-0}, ISSN = {1868-8969}, year = {2020}, volume = {152}, editor = {Fern\'{a}ndez, Maribel and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.36}, URN = {urn:nbn:de:0030-drops-116792}, doi = {10.4230/LIPIcs.CSL.2020.36}, annote = {Keywords: Dynamic complexity, parameterised complexity} }
Published in: Dagstuhl Reports, Volume 9, Issue 3 (2019)
Anna Gál, Rahul Santhanam, and Till Tantau. Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121). In Dagstuhl Reports, Volume 9, Issue 3, pp. 64-82, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@Article{gal_et_al:DagRep.9.3.64, author = {G\'{a}l, Anna and Santhanam, Rahul and Tantau, Till}, title = {{Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121)}}, pages = {64--82}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2019}, volume = {9}, number = {3}, editor = {G\'{a}l, Anna and Santhanam, Rahul and Tantau, Till}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.3.64}, URN = {urn:nbn:de:0030-drops-112920}, doi = {10.4230/DagRep.9.3.64}, annote = {Keywords: circuit complexity, communication complexity, computational complexity, parametrisation, randomness} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Max Bannach and Till Tantau. On the Descriptive Complexity of Color Coding. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 11:1-11:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{bannach_et_al:LIPIcs.STACS.2019.11, author = {Bannach, Max and Tantau, Till}, title = {{On the Descriptive Complexity of Color Coding}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {11:1--11:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.11}, URN = {urn:nbn:de:0030-drops-102509}, doi = {10.4230/LIPIcs.STACS.2019.11}, annote = {Keywords: color coding, descriptive complexity, fixed-parameter tractability, quantifier elimination, para-AC^0} }
Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
Max Bannach and Till Tantau. Computing Kernels in Parallel: Lower and Upper Bounds. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 13:1-13:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{bannach_et_al:LIPIcs.IPEC.2018.13, author = {Bannach, Max and Tantau, Till}, title = {{Computing Kernels in Parallel: Lower and Upper Bounds}}, booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)}, pages = {13:1--13:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-084-2}, ISSN = {1868-8969}, year = {2019}, volume = {115}, editor = {Paul, Christophe and Pilipczuk, Michal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.13}, URN = {urn:nbn:de:0030-drops-102148}, doi = {10.4230/LIPIcs.IPEC.2018.13}, annote = {Keywords: parallel computation, fixed-parameter tractability, kernelization} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Max Bannach and Till Tantau. Computing Hitting Set Kernels By AC^0-Circuits. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 9:1-9:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{bannach_et_al:LIPIcs.STACS.2018.9, author = {Bannach, Max and Tantau, Till}, title = {{Computing Hitting Set Kernels By AC^0-Circuits}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {9:1--9:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.9}, URN = {urn:nbn:de:0030-drops-84998}, doi = {10.4230/LIPIcs.STACS.2018.9}, annote = {Keywords: parallel computation, fixed-parameter tractability, kernelization} }
Published in: Dagstuhl Reports, Volume 7, Issue 3 (2017)
Anna Gál, Michal Koucký, Oded Regev, and Till Tantau. Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121). In Dagstuhl Reports, Volume 7, Issue 3, pp. 45-69, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@Article{gal_et_al:DagRep.7.3.45, author = {G\'{a}l, Anna and Kouck\'{y}, Michal and Regev, Oded and Tantau, Till}, title = {{Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121)}}, pages = {45--69}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2017}, volume = {7}, number = {3}, editor = {G\'{a}l, Anna and Kouck\'{y}, Michal and Regev, Oded and Tantau, Till}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.3.45}, URN = {urn:nbn:de:0030-drops-73611}, doi = {10.4230/DagRep.7.3.45}, annote = {Keywords: Computational Complexity} }
Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Till Tantau. Applications of Algorithmic Metatheorems to Space Complexity and Parallelism (Invited Talk). In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 4:1-4:4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{tantau:LIPIcs.STACS.2017.4, author = {Tantau, Till}, title = {{Applications of Algorithmic Metatheorems to Space Complexity and Parallelism}}, booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)}, pages = {4:1--4:4}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-028-6}, ISSN = {1868-8969}, year = {2017}, volume = {66}, editor = {Vollmer, Heribert and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.4}, URN = {urn:nbn:de:0030-drops-70303}, doi = {10.4230/LIPIcs.STACS.2017.4}, annote = {Keywords: Algorithmic metatheorems, Courcelle’s Theorem, tree width, monadic second-order logic, logarithmic space, parallel computations} }
Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Max Bannach and Till Tantau. Parallel Multivariate Meta-Theorems. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 4:1-4:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{bannach_et_al:LIPIcs.IPEC.2016.4, author = {Bannach, Max and Tantau, Till}, title = {{Parallel Multivariate Meta-Theorems}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, pages = {4:1--4:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-023-1}, ISSN = {1868-8969}, year = {2017}, volume = {63}, editor = {Guo, Jiong and Hermelin, Danny}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.4}, URN = {urn:nbn:de:0030-drops-69227}, doi = {10.4230/LIPIcs.IPEC.2016.4}, annote = {Keywords: Parallel computation, FPT, meta-theorems, tree width, tree depth} }
Feedback for Dagstuhl Publishing