Published in: LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)
Florent Capelli and Oliver Irwin. Direct Access for Conjunctive Queries with Negations. In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{capelli_et_al:LIPIcs.ICDT.2024.13, author = {Capelli, Florent and Irwin, Oliver}, title = {{Direct Access for Conjunctive Queries with Negations}}, booktitle = {27th International Conference on Database Theory (ICDT 2024)}, pages = {13:1--13:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-312-6}, ISSN = {1868-8969}, year = {2024}, volume = {290}, editor = {Cormode, Graham and Shekelyan, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.13}, URN = {urn:nbn:de:0030-drops-197958}, doi = {10.4230/LIPIcs.ICDT.2024.13}, annote = {Keywords: Conjunctive queries, factorized databases, direct access, hypertree decomposition} }
Published in: LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)
Pankaj K. Agarwal, Rahul Raychaudhury, Stavros Sintos, and Jun Yang. Computing Data Distribution from Query Selectivities. In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{agarwal_et_al:LIPIcs.ICDT.2024.18, author = {Agarwal, Pankaj K. and Raychaudhury, Rahul and Sintos, Stavros and Yang, Jun}, title = {{Computing Data Distribution from Query Selectivities}}, booktitle = {27th International Conference on Database Theory (ICDT 2024)}, pages = {18:1--18:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-312-6}, ISSN = {1868-8969}, year = {2024}, volume = {290}, editor = {Cormode, Graham and Shekelyan, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.18}, URN = {urn:nbn:de:0030-drops-198007}, doi = {10.4230/LIPIcs.ICDT.2024.18}, annote = {Keywords: selectivity queries, discrete distributions, Multiplicative Weights Update, eps-approximation, learnable functions, depth problem, arrangement} }
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Omkar Baraskar, Agrim Dewan, and Chandan Saha. Testing Equivalence to Design Polynomials. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 9:1-9:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{baraskar_et_al:LIPIcs.STACS.2024.9, author = {Baraskar, Omkar and Dewan, Agrim and Saha, Chandan}, title = {{Testing Equivalence to Design Polynomials}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {9:1--9:22}, 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.9}, URN = {urn:nbn:de:0030-drops-197193}, doi = {10.4230/LIPIcs.STACS.2024.9}, annote = {Keywords: Polynomial equivalence, design polynomials, graph isomorphism, vector space decomposition} }
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Stéphane Bessy, Stéphan Thomassé, and Laurent Viennot. Temporalizing Digraphs via Linear-Size Balanced Bi-Trees. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 13:1-13:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bessy_et_al:LIPIcs.STACS.2024.13, author = {Bessy, St\'{e}phane and Thomass\'{e}, St\'{e}phan and Viennot, Laurent}, title = {{Temporalizing Digraphs via Linear-Size Balanced Bi-Trees}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {13:1--13:12}, 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.13}, URN = {urn:nbn:de:0030-drops-197235}, doi = {10.4230/LIPIcs.STACS.2024.13}, annote = {Keywords: digraph, temporal graph, temporalization, bi-tree, #1\{in-branching, out-branching, in-tree, out-tree\}, forward connected pairs, left-maximal DFS} }
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Philip Bille, Inge Li Gørtz, Moshe Lewenstein, Solon P. Pissis, Eva Rotenberg, and Teresa Anna Steiner. Gapped String Indexing in Subquadratic Space and Sublinear Query Time. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bille_et_al:LIPIcs.STACS.2024.16, author = {Bille, Philip and G{\o}rtz, Inge Li and Lewenstein, Moshe and Pissis, Solon P. and Rotenberg, Eva and Steiner, Teresa Anna}, title = {{Gapped String Indexing in Subquadratic Space and Sublinear Query Time}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {16:1--16:21}, 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.16}, URN = {urn:nbn:de:0030-drops-197262}, doi = {10.4230/LIPIcs.STACS.2024.16}, annote = {Keywords: data structures, string indexing, indexing with gaps, two patterns} }
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Julian D'Costa, Joël Ouaknine, and James Worrell. Nonnegativity Problems for Matrix Semigroups. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dcosta_et_al:LIPIcs.STACS.2024.27, author = {D'Costa, Julian and Ouaknine, Jo\"{e}l and Worrell, James}, title = {{Nonnegativity Problems for Matrix Semigroups}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {27:1--27:16}, 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.27}, URN = {urn:nbn:de:0030-drops-197371}, doi = {10.4230/LIPIcs.STACS.2024.27}, annote = {Keywords: Decidability, Linear Recurrence Sequences, Schanuel’s Conjecture} }
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Franziska Eberle. O(1/ε) Is the Answer in Online Weighted Throughput Maximization. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{eberle:LIPIcs.STACS.2024.32, author = {Eberle, Franziska}, title = {{O(1/\epsilon) Is the Answer in Online Weighted Throughput Maximization}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {32:1--32:15}, 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.32}, URN = {urn:nbn:de:0030-drops-197428}, doi = {10.4230/LIPIcs.STACS.2024.32}, annote = {Keywords: Deadline scheduling, weighted throughput, online algorithms, competitive analysis} }
Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Daniel Neuen. Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 53:1-53:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{neuen:LIPIcs.STACS.2024.53, author = {Neuen, Daniel}, title = {{Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width}}, booktitle = {41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)}, pages = {53:1--53:12}, 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.53}, URN = {urn:nbn:de:0030-drops-197630}, doi = {10.4230/LIPIcs.STACS.2024.53}, annote = {Keywords: homomorphism indistinguishability, tree-width, Weisfeiler-Leman algorithm, subgraph counts} }
Published in: OASIcs, Volume 117, Fifth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2024)
Khalil Esper and Jürgen Teich. History-Based Run-Time Requirement Enforcement of Non-Functional Properties on MPSoCs. In Fifth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2024). Open Access Series in Informatics (OASIcs), Volume 117, pp. 4:1-4:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{esper_et_al:OASIcs.NG-RES.2024.4, author = {Esper, Khalil and Teich, J\"{u}rgen}, title = {{History-Based Run-Time Requirement Enforcement of Non-Functional Properties on MPSoCs}}, booktitle = {Fifth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2024)}, pages = {4:1--4:11}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-313-3}, ISSN = {2190-6807}, year = {2024}, volume = {117}, editor = {Yomsi, Patrick Meumeu and Wildermann, Stefan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.NG-RES.2024.4}, URN = {urn:nbn:de:0030-drops-197074}, doi = {10.4230/OASIcs.NG-RES.2024.4}, annote = {Keywords: Verification, Runtime Requirement Enforcement, History, Latency} }
Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)
Geoffrey Cruttwell and Jean-Simon Pacaud Lemay. Reverse Tangent Categories. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 21:1-21:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{cruttwell_et_al:LIPIcs.CSL.2024.21, author = {Cruttwell, Geoffrey and Lemay, Jean-Simon Pacaud}, title = {{Reverse Tangent Categories}}, booktitle = {32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)}, pages = {21:1--21:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-310-2}, ISSN = {1868-8969}, year = {2024}, volume = {288}, editor = {Murano, Aniello and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.21}, URN = {urn:nbn:de:0030-drops-196644}, doi = {10.4230/LIPIcs.CSL.2024.21}, annote = {Keywords: Tangent Categories, Reverse Tangent Categories, Reverse Differential Categories, Categorical Machine Learning} }
Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)
Eldar Fischer and Johann A. Makowsky. Extensions and Limits of the Specker-Blatter Theorem. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 26:1-26:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{fischer_et_al:LIPIcs.CSL.2024.26, author = {Fischer, Eldar and Makowsky, Johann A.}, title = {{Extensions and Limits of the Specker-Blatter Theorem}}, booktitle = {32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)}, pages = {26:1--26:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-310-2}, ISSN = {1868-8969}, year = {2024}, volume = {288}, editor = {Murano, Aniello and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.26}, URN = {urn:nbn:de:0030-drops-196694}, doi = {10.4230/LIPIcs.CSL.2024.26}, annote = {Keywords: Specker-Blatter Theorem, Monadic Second Order Logic, MC-finiteness} }
Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)
Laura Fontanella, Guillaume Geoffroy, and Richard Matthews. Realizability Models for Large Cardinals. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{fontanella_et_al:LIPIcs.CSL.2024.28, author = {Fontanella, Laura and Geoffroy, Guillaume and Matthews, Richard}, title = {{Realizability Models for Large Cardinals}}, booktitle = {32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)}, pages = {28:1--28:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-310-2}, ISSN = {1868-8969}, year = {2024}, volume = {288}, editor = {Murano, Aniello and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.28}, URN = {urn:nbn:de:0030-drops-196715}, doi = {10.4230/LIPIcs.CSL.2024.28}, annote = {Keywords: Logic, Classical Realizability, Set Theory, Large Cardinals} }
Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)
Éric Goubault, Roman Kniazev, and Jérémy Ledent. A Many-Sorted Epistemic Logic for Chromatic Hypergraphs. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 30:1-30:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{goubault_et_al:LIPIcs.CSL.2024.30, author = {Goubault, \'{E}ric and Kniazev, Roman and Ledent, J\'{e}r\'{e}my}, title = {{A Many-Sorted Epistemic Logic for Chromatic Hypergraphs}}, booktitle = {32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)}, pages = {30:1--30:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-310-2}, ISSN = {1868-8969}, year = {2024}, volume = {288}, editor = {Murano, Aniello and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.30}, URN = {urn:nbn:de:0030-drops-196730}, doi = {10.4230/LIPIcs.CSL.2024.30}, annote = {Keywords: Modal logics, epistemic logics, multi-agent systems, hypergraphs} }
Published in: Dagstuhl Reports, Volume 13, Issue 6 (2024)
Marijn J. H. Heule, Inês Lynce, Stefan Szeider, and Andre Schidler. SAT Encodings and Beyond (Dagstuhl Seminar 23261). In Dagstuhl Reports, Volume 13, Issue 6, pp. 106-122, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@Article{heule_et_al:DagRep.13.6.106, author = {Heule, Marijn J. H. and Lynce, In\^{e}s and Szeider, Stefan and Schidler, Andre}, title = {{SAT Encodings and Beyond (Dagstuhl Seminar 23261)}}, pages = {106--122}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2024}, volume = {13}, number = {6}, editor = {Heule, Marijn J. H. and Lynce, In\^{e}s and Szeider, Stefan and Schidler, Andre}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.13.6.106}, URN = {urn:nbn:de:0030-drops-196409}, doi = {10.4230/DagRep.13.6.106}, annote = {Keywords: constraint propagation, lower and upper bounds, problem formulation, propositional satisfiability, symmetry breaking} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Pavel Hubáček, Erfan Khaniki, and Neil Thapen. TFNP Intersections Through the Lens of Feasible Disjunction. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 63:1-63:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hubacek_et_al:LIPIcs.ITCS.2024.63, author = {Hub\'{a}\v{c}ek, Pavel and Khaniki, Erfan and Thapen, Neil}, title = {{TFNP Intersections Through the Lens of Feasible Disjunction}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {63:1--63: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.63}, URN = {urn:nbn:de:0030-drops-195917}, doi = {10.4230/LIPIcs.ITCS.2024.63}, annote = {Keywords: TFNP, feasible disjunction, proof complexity, TFNP intersection classes} }
Feedback for Dagstuhl Publishing