Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Pavel Veselý. Fully-Scalable MPC Algorithms for Clustering in High Dimension. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{czumaj_et_al:LIPIcs.ICALP.2024.50, author = {Czumaj, Artur and Gao, Guichen and Jiang, Shaofeng H.-C. and Krauthgamer, Robert and Vesel\'{y}, Pavel}, title = {{Fully-Scalable MPC Algorithms for Clustering in High Dimension}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {50:1--50:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.50}, URN = {urn:nbn:de:0030-drops-201938}, doi = {10.4230/LIPIcs.ICALP.2024.50}, annote = {Keywords: Massively parallel computing, high dimension, facility location, k-median, k-means} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Benjamin Scheidt. On Homomorphism Indistinguishability and Hypertree Depth. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 152:1-152:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{scheidt:LIPIcs.ICALP.2024.152, author = {Scheidt, Benjamin}, title = {{On Homomorphism Indistinguishability and Hypertree Depth}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {152:1--152:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.152}, URN = {urn:nbn:de:0030-drops-202958}, doi = {10.4230/LIPIcs.ICALP.2024.152}, annote = {Keywords: homomorphism indistinguishability, counting logics, guarded logics, hypergraphs, incidence graphs, tree depth, elimination forest, hypertree width} }
Published in: Dagstuhl Manifestos, Volume 10, Issue 1 (2024)
James P. Delgrande, Birte Glimm, Thomas Meyer, Miroslaw Truszczynski, and Frank Wolter. Current and Future Challenges in Knowledge Representation and Reasoning (Dagstuhl Perspectives Workshop 22282). In Dagstuhl Manifestos, Volume 10, Issue 1, pp. 1-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@Article{delgrande_et_al:DagMan.10.1.1, author = {Delgrande, James P. and Glimm, Birte and Meyer, Thomas and Truszczynski, Miroslaw and Wolter, Frank}, title = {{Current and Future Challenges in Knowledge Representation and Reasoning (Dagstuhl Perspectives Workshop 22282)}}, pages = {1--61}, journal = {Dagstuhl Manifestos}, ISSN = {2193-2433}, year = {2024}, volume = {10}, number = {1}, editor = {Delgrande, James P. and Glimm, Birte and Meyer, Thomas and Truszczynski, Miroslaw and Wolter, Frank}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagMan.10.1.1}, URN = {urn:nbn:de:0030-drops-201403}, doi = {10.4230/DagMan.10.1.1}, annote = {Keywords: Knowledge representation and reasoning, Applications of logics, Declarative representations, Formal logic} }
Published in: OASIcs, Volume 119, The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen (2024)
Dan Suciu. Different Differences in Semirings. In The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen. Open Access Series in Informatics (OASIcs), Volume 119, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{suciu:OASIcs.Tannen.10, author = {Suciu, Dan}, title = {{Different Differences in Semirings}}, booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen}, pages = {10:1--10:20}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-320-1}, ISSN = {2190-6807}, year = {2024}, volume = {119}, editor = {Amarilli, Antoine and Deutsch, Alin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.10}, URN = {urn:nbn:de:0030-drops-201062}, doi = {10.4230/OASIcs.Tannen.10}, annote = {Keywords: Semirings, K-relations} }
Published in: TGDK, Volume 2, Issue 1 (2024): Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge, Volume 2, Issue 1
Pieter Bonte, Jean-Paul Calbimonte, Daniel de Leng, Daniele Dell'Aglio, Emanuele Della Valle, Thomas Eiter, Federico Giannini, Fredrik Heintz, Konstantin Schekotihin, Danh Le-Phuoc, Alessandra Mileo, Patrik Schneider, Riccardo Tommasini, Jacopo Urbani, and Giacomo Ziffer. Grounding Stream Reasoning Research. In Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge (TGDK), Volume 2, Issue 1, pp. 2:1-2:47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@Article{bonte_et_al:TGDK.2.1.2, author = {Bonte, Pieter and Calbimonte, Jean-Paul and de Leng, Daniel and Dell'Aglio, Daniele and Della Valle, Emanuele and Eiter, Thomas and Giannini, Federico and Heintz, Fredrik and Schekotihin, Konstantin and Le-Phuoc, Danh and Mileo, Alessandra and Schneider, Patrik and Tommasini, Riccardo and Urbani, Jacopo and Ziffer, Giacomo}, title = {{Grounding Stream Reasoning Research}}, journal = {Transactions on Graph Data and Knowledge}, pages = {2:1--2:47}, ISSN = {2942-7517}, year = {2024}, volume = {2}, number = {1}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/TGDK.2.1.2}, URN = {urn:nbn:de:0030-drops-198597}, doi = {10.4230/TGDK.2.1.2}, annote = {Keywords: Stream Reasoning, Stream Processing, RDF streams, Streaming Linked Data, Continuous query processing, Temporal Logics, High-performance computing, Databases} }
Published in: LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)
Antoine Amarilli, Timothy van Bremen, and Kuldeep S. Meel. Conjunctive Queries on Probabilistic Graphs: The Limits of Approximability. In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 15:1-15:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{amarilli_et_al:LIPIcs.ICDT.2024.15, author = {Amarilli, Antoine and van Bremen, Timothy and Meel, Kuldeep S.}, title = {{Conjunctive Queries on Probabilistic Graphs: The Limits of Approximability}}, booktitle = {27th International Conference on Database Theory (ICDT 2024)}, pages = {15:1--15: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.15}, URN = {urn:nbn:de:0030-drops-197978}, doi = {10.4230/LIPIcs.ICDT.2024.15}, annote = {Keywords: Probabilistic query evaluation, tuple-independent databases, approximation} }
Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)
Kyle Deeds, Dan Suciu, Magda Balazinska, and Walter Cai. Degree Sequence Bound for Join Cardinality Estimation. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{deeds_et_al:LIPIcs.ICDT.2023.8, author = {Deeds, Kyle and Suciu, Dan and Balazinska, Magda and Cai, Walter}, title = {{Degree Sequence Bound for Join Cardinality Estimation}}, booktitle = {26th International Conference on Database Theory (ICDT 2023)}, pages = {8:1--8:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-270-9}, ISSN = {1868-8969}, year = {2023}, volume = {255}, editor = {Geerts, Floris and Vandevoort, Brecht}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.8}, URN = {urn:nbn:de:0030-drops-177508}, doi = {10.4230/LIPIcs.ICDT.2023.8}, annote = {Keywords: Cardinality Estimation, Cardinality Bounding, Degree Bounds, Functional Approximation, Query Planning, Berge-Acyclic Queries} }
Published in: Dagstuhl Reports, Volume 12, Issue 7 (2023)
Phokion G. Kolaitis, Andrej E. Romashchenko, Milan Studený, Dan Suciu, and Tobias A. Boege. Algorithmic Aspects of Information Theory (Dagstuhl Seminar 22301). In Dagstuhl Reports, Volume 12, Issue 7, pp. 180-204, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@Article{kolaitis_et_al:DagRep.12.7.180, author = {Kolaitis, Phokion G. and Romashchenko, Andrej E. and Studen\'{y}, Milan and Suciu, Dan and Boege, Tobias A.}, title = {{Algorithmic Aspects of Information Theory (Dagstuhl Seminar 22301)}}, pages = {180--204}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2023}, volume = {12}, number = {7}, editor = {Kolaitis, Phokion G. and Romashchenko, Andrej E. and Studen\'{y}, Milan and Suciu, Dan and Boege, Tobias A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.7.180}, URN = {urn:nbn:de:0030-drops-176155}, doi = {10.4230/DagRep.12.7.180}, annote = {Keywords: Information theory, Information inequalities, Conditional independence structures, Database query evaluation and containment, Decision problems} }
Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)
Hung Q. Ngo. On an Information Theoretic Approach to Cardinality Estimation (Invited Talk). In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 1:1-1:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{ngo:LIPIcs.ICDT.2022.1, author = {Ngo, Hung Q.}, title = {{On an Information Theoretic Approach to Cardinality Estimation}}, booktitle = {25th International Conference on Database Theory (ICDT 2022)}, pages = {1:1--1:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-223-5}, ISSN = {1868-8969}, year = {2022}, volume = {220}, editor = {Olteanu, Dan and Vortmeier, Nils}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.1}, URN = {urn:nbn:de:0030-drops-158750}, doi = {10.4230/LIPIcs.ICDT.2022.1}, annote = {Keywords: Cardinality Estimation, Information Theory, Polymatroid Bound, Worst-case Optimal Join} }
Published in: LIPIcs, Volume 186, 24th International Conference on Database Theory (ICDT 2021)
Antoine Amarilli and Benny Kimelfeld. Uniform Reliability of Self-Join-Free Conjunctive Queries. In 24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{amarilli_et_al:LIPIcs.ICDT.2021.17, author = {Amarilli, Antoine and Kimelfeld, Benny}, title = {{Uniform Reliability of Self-Join-Free Conjunctive Queries}}, booktitle = {24th International Conference on Database Theory (ICDT 2021)}, pages = {17:1--17:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-179-5}, ISSN = {1868-8969}, year = {2021}, volume = {186}, editor = {Yi, Ke and Wei, Zhewei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2021.17}, URN = {urn:nbn:de:0030-drops-137252}, doi = {10.4230/LIPIcs.ICDT.2021.17}, annote = {Keywords: Hierarchical conjunctive queries, query reliability, tuple-independent database, counting problems, #P-hardness} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Mahmoud Abo Khamis, Phokion G. Kolaitis, Hung Q. Ngo, and Dan Suciu. Decision Problems in Information Theory. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 106:1-106:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{abokhamis_et_al:LIPIcs.ICALP.2020.106, author = {Abo Khamis, Mahmoud and Kolaitis, Phokion G. and Ngo, Hung Q. and Suciu, Dan}, title = {{Decision Problems in Information Theory}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {106:1--106:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.106}, URN = {urn:nbn:de:0030-drops-125137}, doi = {10.4230/LIPIcs.ICALP.2020.106}, annote = {Keywords: Information theory, decision problems, arithmetical hierarchy, entropic functions} }
Published in: LIPIcs, Volume 155, 23rd International Conference on Database Theory (ICDT 2020)
Batya Kenig and Dan Suciu. Integrity Constraints Revisited: From Exact to Approximate Implication. In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kenig_et_al:LIPIcs.ICDT.2020.18, author = {Kenig, Batya and Suciu, Dan}, title = {{Integrity Constraints Revisited: From Exact to Approximate Implication}}, booktitle = {23rd International Conference on Database Theory (ICDT 2020)}, pages = {18:1--18:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-139-9}, ISSN = {1868-8969}, year = {2020}, volume = {155}, editor = {Lutz, Carsten and Jung, Jean Christoph}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2020.18}, URN = {urn:nbn:de:0030-drops-119420}, doi = {10.4230/LIPIcs.ICDT.2020.18}, annote = {Keywords: Integrity constraints, The implication problem} }
Published in: LIPIcs, Volume 127, 22nd International Conference on Database Theory (ICDT 2019)
Mahmoud Abo Khamis, Hung Q. Ngo, Dan Olteanu, and Dan Suciu. Boolean Tensor Decomposition for Conjunctive Queries with Negation. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 21:1-21:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{abokhamis_et_al:LIPIcs.ICDT.2019.21, author = {Abo Khamis, Mahmoud and Ngo, Hung Q. and Olteanu, Dan and Suciu, Dan}, title = {{Boolean Tensor Decomposition for Conjunctive Queries with Negation}}, booktitle = {22nd International Conference on Database Theory (ICDT 2019)}, pages = {21:1--21:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-101-6}, ISSN = {1868-8969}, year = {2019}, volume = {127}, editor = {Barcelo, Pablo and Calautti, Marco}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2019.21}, URN = {urn:nbn:de:0030-drops-103236}, doi = {10.4230/LIPIcs.ICDT.2019.21}, annote = {Keywords: color-coding, combined complexity, negation, query evaluation} }
Published in: Dagstuhl Manifestos, Volume 7, Issue 1 (2018)
Serge Abiteboul, Marcelo Arenas, Pablo Barceló, Meghyn Bienvenu, Diego Calvanese, Claire David, Richard Hull, Eyke Hüllermeier, Benny Kimelfeld, Leonid Libkin, Wim Martens, Tova Milo, Filip Murlak, Frank Neven, Magdalena Ortiz, Thomas Schwentick, Julia Stoyanovich, Jianwen Su, Dan Suciu, Victor Vianu, and Ke Yi. Research Directions for Principles of Data Management (Dagstuhl Perspectives Workshop 16151). In Dagstuhl Manifestos, Volume 7, Issue 1, pp. 1-29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@Article{abiteboul_et_al:DagMan.7.1.1, author = {Abiteboul, Serge and Arenas, Marcelo and Barcel\'{o}, Pablo and Bienvenu, Meghyn and Calvanese, Diego and David, Claire and Hull, Richard and H\"{u}llermeier, Eyke and Kimelfeld, Benny and Libkin, Leonid and Martens, Wim and Milo, Tova and Murlak, Filip and Neven, Frank and Ortiz, Magdalena and Schwentick, Thomas and Stoyanovich, Julia and Su, Jianwen and Suciu, Dan and Vianu, Victor and Yi, Ke}, title = {{Research Directions for Principles of Data Management (Dagstuhl Perspectives Workshop 16151)}}, pages = {1--29}, journal = {Dagstuhl Manifestos}, ISSN = {2193-2433}, year = {2018}, volume = {7}, number = {1}, editor = {Abiteboul, Serge and Arenas, Marcelo and Barcel\'{o}, Pablo and Bienvenu, Meghyn and Calvanese, Diego and David, Claire and Hull, Richard and H\"{u}llermeier, Eyke and Kimelfeld, Benny and Libkin, Leonid and Martens, Wim and Milo, Tova and Murlak, Filip and Neven, Frank and Ortiz, Magdalena and Schwentick, Thomas and Stoyanovich, Julia and Su, Jianwen and Suciu, Dan and Vianu, Victor and Yi, Ke}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagMan.7.1.1}, URN = {urn:nbn:de:0030-drops-86772}, doi = {10.4230/DagMan.7.1.1}, annote = {Keywords: database theory, principles of data management, query languages, efficient query processing, query optimization, heterogeneous data, uncertainty, knowledge-enriched data management, machine learning, workflows, human-related data, ethics} }
Published in: Dagstuhl Reports, Volume 7, Issue 9 (2018)
Adnan Darwiche, Pierre Marquis, Dan Suciu, and Stefan Szeider. Recent Trends in Knowledge Compilation (Dagstuhl Seminar 17381). In Dagstuhl Reports, Volume 7, Issue 9, pp. 62-85, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@Article{darwiche_et_al:DagRep.7.9.62, author = {Darwiche, Adnan and Marquis, Pierre and Suciu, Dan and Szeider, Stefan}, title = {{Recent Trends in Knowledge Compilation (Dagstuhl Seminar 17381)}}, pages = {62--85}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2018}, volume = {7}, number = {9}, editor = {Darwiche, Adnan and Marquis, Pierre and Suciu, Dan and Szeider, Stefan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.9.62}, URN = {urn:nbn:de:0030-drops-85896}, doi = {10.4230/DagRep.7.9.62}, annote = {Keywords: Knowledge compilation, Constraints, Preprocessing, Probabilistic databases, Model counting} }