Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Nicolás Bitar. Contributions to the Domino Problem: Seeding, Recurrence and Satisfiability. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bitar:LIPIcs.STACS.2024.17, author = {Bitar, Nicol\'{a}s}, title = {{Contributions to the Domino Problem: Seeding, Recurrence and Satisfiability}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {17:1--17:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.17}, URN = {urn:nbn:de:0030-drops-197275}, doi = {10.4230/LIPIcs.STACS.2024.17}, annote = {Keywords: Tilings, Domino problem, SAT, Computability, Finitely generated groups} }
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Nicolas Bousquet, Laurent Feuilloley, and Sébastien Zeitoun. Local Certification of Local Properties: Tight Bounds, Trade-Offs and New Parameters. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bousquet_et_al:LIPIcs.STACS.2024.21, author = {Bousquet, Nicolas and Feuilloley, Laurent and Zeitoun, S\'{e}bastien}, title = {{Local Certification of Local Properties: Tight Bounds, Trade-Offs and New Parameters}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {21:1--21:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.21}, URN = {urn:nbn:de:0030-drops-197317}, doi = {10.4230/LIPIcs.STACS.2024.21}, annote = {Keywords: Local certification, local properties, proof-labeling schemes, locally checkable proofs, optimal certification size, colorability, dominating set, perfect matching, fault-tolerance, graph structure} }
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Marek Filakovský, Tamio-Vesa Nakajima, Jakub Opršal, Gianluca Tasinato, and Uli Wagner. Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 34:1-34:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{filakovsky_et_al:LIPIcs.STACS.2024.34, author = {Filakovsk\'{y}, Marek and Nakajima, Tamio-Vesa and Opr\v{s}al, Jakub and Tasinato, Gianluca and Wagner, Uli}, title = {{Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {34:1--34:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.34}, URN = {urn:nbn:de:0030-drops-197445}, doi = {10.4230/LIPIcs.STACS.2024.34}, annote = {Keywords: constraint satisfaction problem, hypergraph colouring, promise problem, topological methods} }
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Stefan Göller and Nathan Grosshans. The AC⁰-Complexity of Visibly Pushdown Languages. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 38:1-38:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{goller_et_al:LIPIcs.STACS.2024.38, author = {G\"{o}ller, Stefan and Grosshans, Nathan}, title = {{The AC⁰-Complexity of Visibly Pushdown Languages}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {38:1--38:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.38}, URN = {urn:nbn:de:0030-drops-197483}, doi = {10.4230/LIPIcs.STACS.2024.38}, annote = {Keywords: Visibly pushdown languages, Circuit Complexity, AC0} }
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
David G. Harris and N. S. Narayanaswamy. A Faster Algorithm for Vertex Cover Parameterized by Solution Size. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{harris_et_al:LIPIcs.STACS.2024.40, author = {Harris, David G. and Narayanaswamy, N. S.}, title = {{A Faster Algorithm for Vertex Cover Parameterized by Solution Size}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {40:1--40:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.40}, URN = {urn:nbn:de:0030-drops-197508}, doi = {10.4230/LIPIcs.STACS.2024.40}, annote = {Keywords: Vertex cover, FPT, Graph algorithm} }
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, and Peter Strulo. Decremental Sensitivity Oracles for Covering and Packing Minors. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 44:1-44:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kanesh_et_al:LIPIcs.STACS.2024.44, author = {Kanesh, Lawqueen and Panolan, Fahad and Ramanujan, M. S. and Strulo, Peter}, title = {{Decremental Sensitivity Oracles for Covering and Packing Minors}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {44:1--44:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-311-9}, ISSN = {1868-8969}, year = {2024}, volume = {289}, editor = {Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.44}, URN = {urn:nbn:de:0030-drops-197544}, doi = {10.4230/LIPIcs.STACS.2024.44}, annote = {Keywords: Sensitivity oracles, Data Structures, FPT algorithms} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Karl Bringmann, Allan Grønlund, Marvin Künnemann, and Kasper Green Larsen. The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 22:1-22:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bringmann_et_al:LIPIcs.ITCS.2024.22, author = {Bringmann, Karl and Gr{\o}nlund, Allan and K\"{u}nnemann, Marvin and Larsen, Kasper Green}, title = {{The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {22:1--22:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.22}, URN = {urn:nbn:de:0030-drops-195500}, doi = {10.4230/LIPIcs.ITCS.2024.22}, annote = {Keywords: Fine-grained complexity theory, non-deterministic finite automata} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Atanas Dinev and S. Matthew Weinberg. Simple and Optimal Online Contention Resolution Schemes for k-Uniform Matroids. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 39:1-39:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dinev_et_al:LIPIcs.ITCS.2024.39, author = {Dinev, Atanas and Weinberg, S. Matthew}, title = {{Simple and Optimal Online Contention Resolution Schemes for k-Uniform Matroids}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {39:1--39:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.39}, URN = {urn:nbn:de:0030-drops-195677}, doi = {10.4230/LIPIcs.ITCS.2024.39}, annote = {Keywords: online contention resolutions schemes, prophet inequalities, online algorithms, approximation algorithms} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif, Morgan Shirley, and Adi Shraibman. An Improved Protocol for ExactlyN with More Than 3 Players. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 58:1-58:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hambardzumyan_et_al:LIPIcs.ITCS.2024.58, author = {Hambardzumyan, Lianna and Pitassi, Toniann and Sherif, Suhail and Shirley, Morgan and Shraibman, Adi}, title = {{An Improved Protocol for ExactlyN with More Than 3 Players}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {58:1--58:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.58}, URN = {urn:nbn:de:0030-drops-195868}, doi = {10.4230/LIPIcs.ITCS.2024.58}, annote = {Keywords: Corner-free sets, number-on-forehead communication} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Tanmay Inamdar, Madhumita Kundu, Pekka Parviainen, M. S. Ramanujan, and Saket Saurabh. Exponential-Time Approximation Schemes via Compression. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 64:1-64:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{inamdar_et_al:LIPIcs.ITCS.2024.64, author = {Inamdar, Tanmay and Kundu, Madhumita and Parviainen, Pekka and Ramanujan, M. S. and Saurabh, Saket}, title = {{Exponential-Time Approximation Schemes via Compression}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {64:1--64:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.64}, URN = {urn:nbn:de:0030-drops-195920}, doi = {10.4230/LIPIcs.ITCS.2024.64}, annote = {Keywords: Exponential-Time Algorithms, Approximation Algorithms, Graph Algorithms, Cut Problems} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Weihao Kong, Mingda Qiao, and Rajat Sen. A Combinatorial Approach to Robust PCA. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 70:1-70:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kong_et_al:LIPIcs.ITCS.2024.70, author = {Kong, Weihao and Qiao, Mingda and Sen, Rajat}, title = {{A Combinatorial Approach to Robust PCA}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {70:1--70:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.70}, URN = {urn:nbn:de:0030-drops-195984}, doi = {10.4230/LIPIcs.ITCS.2024.70}, annote = {Keywords: Robust PCA, Sparse Recovery, Robust Statistics} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Ofer Neiman and Idan Shabat. On the Size Overhead of Pairwise Spanners. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 83:1-83:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{neiman_et_al:LIPIcs.ITCS.2024.83, author = {Neiman, Ofer and Shabat, Idan}, title = {{On the Size Overhead of Pairwise Spanners}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {83:1--83:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.83}, URN = {urn:nbn:de:0030-drops-196110}, doi = {10.4230/LIPIcs.ITCS.2024.83}, annote = {Keywords: Graph Algorithms, Shortest Paths, Spanners} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Teresa Anna Steiner. Differentially Private Approximate Pattern Matching. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 94:1-94:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{steiner:LIPIcs.ITCS.2024.94, author = {Steiner, Teresa Anna}, title = {{Differentially Private Approximate Pattern Matching}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {94:1--94:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.94}, URN = {urn:nbn:de:0030-drops-196223}, doi = {10.4230/LIPIcs.ITCS.2024.94}, annote = {Keywords: Differential privacy, pattern matching} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Iddo Tzameret and Lu-Ming Zhang. Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 95:1-95:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{tzameret_et_al:LIPIcs.ITCS.2024.95, author = {Tzameret, Iddo and Zhang, Lu-Ming}, title = {{Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {95:1--95:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.95}, URN = {urn:nbn:de:0030-drops-196234}, doi = {10.4230/LIPIcs.ITCS.2024.95}, annote = {Keywords: Pseudorandomness, Cryptography, Natural Proofs, Nondeterminism, Lower bounds} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Mingxun Zhou, Mengshi Zhao, T-H. Hubert Chan, and Elaine Shi. Advanced Composition Theorems for Differential Obliviousness. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 103:1-103:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{zhou_et_al:LIPIcs.ITCS.2024.103, author = {Zhou, Mingxun and Zhao, Mengshi and Chan, T-H. Hubert and Shi, Elaine}, title = {{Advanced Composition Theorems for Differential Obliviousness}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {103:1--103:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.103}, URN = {urn:nbn:de:0030-drops-196315}, doi = {10.4230/LIPIcs.ITCS.2024.103}, annote = {Keywords: Differential Privacy, Oblivious Algorithms} }
Feedback for Dagstuhl Publishing