Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)
Gilles Audemard, Christophe Lecoutre, and Charles Prud'homme. Guiding Backtrack Search by Tracking Variables During Constraint Propagation. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{audemard_et_al:LIPIcs.CP.2023.9, author = {Audemard, Gilles and Lecoutre, Christophe and Prud'homme, Charles}, title = {{Guiding Backtrack Search by Tracking Variables During Constraint Propagation}}, booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)}, pages = {9:1--9:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-300-3}, ISSN = {1868-8969}, year = {2023}, volume = {280}, editor = {Yap, Roland H. C.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.9}, URN = {urn:nbn:de:0030-drops-190461}, doi = {10.4230/LIPIcs.CP.2023.9}, annote = {Keywords: Variable Ordering Heuristics, Variable Weighting} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Philip Bille, Inge Li Gørtz, and Teresa Anna Steiner. String Indexing with Compressed Patterns. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bille_et_al:LIPIcs.STACS.2020.10, author = {Bille, Philip and G{\o}rtz, Inge Li and Steiner, Teresa Anna}, title = {{String Indexing with Compressed Patterns}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {10:1--10:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.10}, URN = {urn:nbn:de:0030-drops-118716}, doi = {10.4230/LIPIcs.STACS.2020.10}, annote = {Keywords: string indexing, compression, pattern matching} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Manuel Lafond, Binhai Zhu, and Peng Zou. The Tandem Duplication Distance Is NP-Hard. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{lafond_et_al:LIPIcs.STACS.2020.15, author = {Lafond, Manuel and Zhu, Binhai and Zou, Peng}, title = {{The Tandem Duplication Distance Is NP-Hard}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {15:1--15:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.15}, URN = {urn:nbn:de:0030-drops-118769}, doi = {10.4230/LIPIcs.STACS.2020.15}, annote = {Keywords: Tandem duplication, Text processing, Formal languages, Computational genomics, FPT algorithms} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Sevag Gharibian, Stephen Piddock, and Justin Yirka. Oracle Complexity Classes and Local Measurements on Physical Hamiltonians. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 20:1-20:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{gharibian_et_al:LIPIcs.STACS.2020.20, author = {Gharibian, Sevag and Piddock, Stephen and Yirka, Justin}, title = {{Oracle Complexity Classes and Local Measurements on Physical Hamiltonians}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {20:1--20:37}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.20}, URN = {urn:nbn:de:0030-drops-118818}, doi = {10.4230/LIPIcs.STACS.2020.20}, annote = {Keywords: Quantum Merlin Arthur (QMA), simulation of local measurement, local Hamiltonian, oracle complexity class, physical Hamiltonians} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
S. Akshay, Nikhil Balaji, Aniket Murhekar, Rohith Varma, and Nikhil Vyas. Near-Optimal Complexity Bounds for Fragments of the Skolem Problem. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{akshay_et_al:LIPIcs.STACS.2020.37, author = {Akshay, S. and Balaji, Nikhil and Murhekar, Aniket and Varma, Rohith and Vyas, Nikhil}, title = {{Near-Optimal Complexity Bounds for Fragments of the Skolem Problem}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {37:1--37:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.37}, URN = {urn:nbn:de:0030-drops-118982}, doi = {10.4230/LIPIcs.STACS.2020.37}, annote = {Keywords: Linear Recurrences, Skolem problem, NP-completeness, Weighted automata} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Andrés Cristi, Mathieu Mari, and Andreas Wiese. Fixed-Parameter Algorithms for Unsplittable Flow Cover. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 42:1-42:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{cristi_et_al:LIPIcs.STACS.2020.42, author = {Cristi, Andr\'{e}s and Mari, Mathieu and Wiese, Andreas}, title = {{Fixed-Parameter Algorithms for Unsplittable Flow Cover}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {42:1--42:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.42}, URN = {urn:nbn:de:0030-drops-119037}, doi = {10.4230/LIPIcs.STACS.2020.42}, annote = {Keywords: Unsplittable Flow Cover, fixed parameter algorithms, approximation algorithms} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Andrés Cristi and Andreas Wiese. Better Approximations for General Caching and UFP-Cover Under Resource Augmentation. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{cristi_et_al:LIPIcs.STACS.2020.44, author = {Cristi, Andr\'{e}s and Wiese, Andreas}, title = {{Better Approximations for General Caching and UFP-Cover Under Resource Augmentation}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {44:1--44:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.44}, URN = {urn:nbn:de:0030-drops-119053}, doi = {10.4230/LIPIcs.STACS.2020.44}, annote = {Keywords: General caching, unsplittable flow cover, approximation algorithm, resource augmentation} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, and Ronald de Wolf. Improved Bounds on Fourier Entropy and Min-Entropy. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{arunachalam_et_al:LIPIcs.STACS.2020.45, author = {Arunachalam, Srinivasan and Chakraborty, Sourav and Kouck\'{y}, Michal and Saurabh, Nitin and de Wolf, Ronald}, title = {{Improved Bounds on Fourier Entropy and Min-Entropy}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {45:1--45:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.45}, URN = {urn:nbn:de:0030-drops-119062}, doi = {10.4230/LIPIcs.STACS.2020.45}, annote = {Keywords: Fourier analysis of Boolean functions, FEI conjecture, query complexity, polynomial approximation, approximate degree, certificate complexity} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Xiang Huang, Jack H. Lutz, Elvira Mayordomo, and Donald M. Stull. Asymptotic Divergences and Strong Dichotomy. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 51:1-51:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{huang_et_al:LIPIcs.STACS.2020.51, author = {Huang, Xiang and Lutz, Jack H. and Mayordomo, Elvira and Stull, Donald M.}, title = {{Asymptotic Divergences and Strong Dichotomy}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {51:1--51:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.51}, URN = {urn:nbn:de:0030-drops-119125}, doi = {10.4230/LIPIcs.STACS.2020.51}, annote = {Keywords: finite-state dimension, finite-state gambler, Kullback-Leibler divergence, normal sequences} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
S. M. Dhannya and N. S. Narayanaswamy. Perfect Resolution of Conflict-Free Colouring of Interval Hypergraphs. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 52:1-52:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{dhannya_et_al:LIPIcs.STACS.2020.52, author = {Dhannya, S. M. and Narayanaswamy, N. S.}, title = {{Perfect Resolution of Conflict-Free Colouring of Interval Hypergraphs}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {52:1--52:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.52}, URN = {urn:nbn:de:0030-drops-119138}, doi = {10.4230/LIPIcs.STACS.2020.52}, annote = {Keywords: Conflict-free Colouring, Interval Hypergraphs} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Shaull Almagor, Joël Ouaknine, and James Worrell. The Semialgebraic Orbit Problem. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{almagor_et_al:LIPIcs.STACS.2019.6, author = {Almagor, Shaull and Ouaknine, Jo\"{e}l and Worrell, James}, title = {{The Semialgebraic Orbit Problem}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {6:1--6:15}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.6}, URN = {urn:nbn:de:0030-drops-102450}, doi = {10.4230/LIPIcs.STACS.2019.6}, annote = {Keywords: linear dynamical systems, Orbit Problem, first order theory of the reals} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Martin Dietzfelbinger and Stefan Walzer. Constant-Time Retrieval with O(log m) Extra Bits. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dietzfelbinger_et_al:LIPIcs.STACS.2019.24, author = {Dietzfelbinger, Martin and Walzer, Stefan}, title = {{Constant-Time Retrieval with O(log m) Extra Bits}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {24:1--24: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.24}, URN = {urn:nbn:de:0030-drops-102639}, doi = {10.4230/LIPIcs.STACS.2019.24}, annote = {Keywords: Retrieval, Hashing, Succinct Data Structure, Randomised Data Structure, Structured Gaussian Elimination, Method of Four Russians} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Eduard Eiben, Dušan Knop, Fahad Panolan, and Ondřej Suchý. Complexity of the Steiner Network Problem with Respect to the Number of Terminals. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{eiben_et_al:LIPIcs.STACS.2019.25, author = {Eiben, Eduard and Knop, Du\v{s}an and Panolan, Fahad and Such\'{y}, Ond\v{r}ej}, title = {{Complexity of the Steiner Network Problem with Respect to the Number of Terminals}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {25:1--25:17}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.25}, URN = {urn:nbn:de:0030-drops-102642}, doi = {10.4230/LIPIcs.STACS.2019.25}, annote = {Keywords: Directed Steiner Network, Planar Graphs, Parameterized Algorithms, Bounded Genus, Exponential Time Hypothesis} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Grzegorz Fabiański, Michał Pilipczuk, Sebastian Siebertz, and Szymon Toruńczyk. Progressive Algorithms for Domination and Independence. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{fabianski_et_al:LIPIcs.STACS.2019.27, author = {Fabia\'{n}ski, Grzegorz and Pilipczuk, Micha{\l} and Siebertz, Sebastian and Toru\'{n}czyk, Szymon}, title = {{Progressive Algorithms for Domination and Independence}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {27:1--27: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.27}, URN = {urn:nbn:de:0030-drops-102660}, doi = {10.4230/LIPIcs.STACS.2019.27}, annote = {Keywords: Dominating Set, Independent Set, nowhere denseness, stability, fixed-parameter tractability} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Kurtuluş Gemici, Elias Koutsoupias, Barnabé Monnot, Christos H. Papadimitriou, and Georgios Piliouras. Wealth Inequality and the Price of Anarchy. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{gemici_et_al:LIPIcs.STACS.2019.31, author = {Gemici, Kurtulu\c{s} and Koutsoupias, Elias and Monnot, Barnab\'{e} and Papadimitriou, Christos H. and Piliouras, Georgios}, title = {{Wealth Inequality and the Price of Anarchy}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {31:1--31: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.31}, URN = {urn:nbn:de:0030-drops-102707}, doi = {10.4230/LIPIcs.STACS.2019.31}, annote = {Keywords: congestion games, inequality} }
Feedback for Dagstuhl Publishing