LIPIcs, Volume 220
ICDT 2022, March 29 to April 1, 2022, Edinburgh, UK (Virtual Conference)
Editors: Dan Olteanu and Nils Vortmeier
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Samir Datta, Asif Khan, and Anish Mukherjee. Dynamic Planar Embedding Is in DynFO. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{datta_et_al:LIPIcs.MFCS.2023.39, author = {Datta, Samir and Khan, Asif and Mukherjee, Anish}, title = {{Dynamic Planar Embedding Is in DynFO}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {39:1--39:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.39}, URN = {urn:nbn:de:0030-drops-185736}, doi = {10.4230/LIPIcs.MFCS.2023.39}, annote = {Keywords: Dynamic Complexity, Planar graphs, Planar embedding} }
Published in: LIPIcs, Volume 252, 31st EACSL Annual Conference on Computer Science Logic (CSL 2023)
Felix Tschirbs, Nils Vortmeier, and Thomas Zeume. Dynamic Complexity of Regular Languages: Big Changes, Small Work. In 31st EACSL Annual Conference on Computer Science Logic (CSL 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 252, pp. 35:1-35:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{tschirbs_et_al:LIPIcs.CSL.2023.35, author = {Tschirbs, Felix and Vortmeier, Nils and Zeume, Thomas}, title = {{Dynamic Complexity of Regular Languages: Big Changes, Small Work}}, booktitle = {31st EACSL Annual Conference on Computer Science Logic (CSL 2023)}, pages = {35:1--35:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-264-8}, ISSN = {1868-8969}, year = {2023}, volume = {252}, editor = {Klin, Bartek and Pimentel, Elaine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2023.35}, URN = {urn:nbn:de:0030-drops-174963}, doi = {10.4230/LIPIcs.CSL.2023.35}, annote = {Keywords: dynamic descriptive complexity, regular languages, batch changes, work} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma, and Raghunath Tewari. Dynamic Meta-Theorems for Distance and Matching. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 118:1-118:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{datta_et_al:LIPIcs.ICALP.2022.118, author = {Datta, Samir and Gupta, Chetan and Jain, Rahul and Mukherjee, Anish and Sharma, Vimal Raj and Tewari, Raghunath}, title = {{Dynamic Meta-Theorems for Distance and Matching}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {118:1--118:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.118}, URN = {urn:nbn:de:0030-drops-164598}, doi = {10.4230/LIPIcs.ICALP.2022.118}, annote = {Keywords: Dynamic Complexity, Distance, Matching, Derandomization, Isolation, Matrix Rank} }
Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)
25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 1-354, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@Proceedings{olteanu_et_al:LIPIcs.ICDT.2022, title = {{LIPIcs, Volume 220, ICDT 2022, Complete Volume}}, booktitle = {25th International Conference on Database Theory (ICDT 2022)}, pages = {1--354}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022}, URN = {urn:nbn:de:0030-drops-158737}, doi = {10.4230/LIPIcs.ICDT.2022}, annote = {Keywords: LIPIcs, Volume 220, ICDT 2022, Complete Volume} }
Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)
25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{olteanu_et_al:LIPIcs.ICDT.2022.0, author = {Olteanu, Dan and Vortmeier, Nils}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {25th International Conference on Database Theory (ICDT 2022)}, pages = {0:i--0:xvi}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.0}, URN = {urn:nbn:de:0030-drops-158745}, doi = {10.4230/LIPIcs.ICDT.2022.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
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-dev.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 220, 25th International Conference on Database Theory (ICDT 2022)
Marcelo Arenas. Counting the Solutions to a Query (Invited Talk). In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{arenas:LIPIcs.ICDT.2022.2, author = {Arenas, Marcelo}, title = {{Counting the Solutions to a Query}}, booktitle = {25th International Conference on Database Theory (ICDT 2022)}, pages = {2:1--2:1}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.2}, URN = {urn:nbn:de:0030-drops-158763}, doi = {10.4230/LIPIcs.ICDT.2022.2}, annote = {Keywords: Counting, query answering, fully polynomial-time randomized approximation scheme} }
Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)
Nofar Carmeli. Answering Unions of Conjunctive Queries with Ideal Time Guarantees (Invited Talk). In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{carmeli:LIPIcs.ICDT.2022.3, author = {Carmeli, Nofar}, title = {{Answering Unions of Conjunctive Queries with Ideal Time Guarantees}}, booktitle = {25th International Conference on Database Theory (ICDT 2022)}, pages = {3:1--3:1}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.3}, URN = {urn:nbn:de:0030-drops-158771}, doi = {10.4230/LIPIcs.ICDT.2022.3}, annote = {Keywords: query evaluation, enumeration, fine-grained complexity, constant delay, union of conjunctive queries} }
Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)
Shay Gershtein, Uri Avron, Ido Guy, Tova Milo, and Slava Novgorodov. On the Hardness of Category Tree Construction. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{gershtein_et_al:LIPIcs.ICDT.2022.4, author = {Gershtein, Shay and Avron, Uri and Guy, Ido and Milo, Tova and Novgorodov, Slava}, title = {{On the Hardness of Category Tree Construction}}, booktitle = {25th International Conference on Database Theory (ICDT 2022)}, pages = {4:1--4:17}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.4}, URN = {urn:nbn:de:0030-drops-158785}, doi = {10.4230/LIPIcs.ICDT.2022.4}, annote = {Keywords: maximum independent set, approximation algorithms, approximation hardness bounds, taxonomy construction, category tree construction} }
Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)
Florent Capelli, Nicolas Crosetti, Joachim Niehren, and Jan Ramon. Linear Programs with Conjunctive Queries. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{capelli_et_al:LIPIcs.ICDT.2022.5, author = {Capelli, Florent and Crosetti, Nicolas and Niehren, Joachim and Ramon, Jan}, title = {{Linear Programs with Conjunctive Queries}}, booktitle = {25th International Conference on Database Theory (ICDT 2022)}, pages = {5:1--5:19}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.5}, URN = {urn:nbn:de:0030-drops-158796}, doi = {10.4230/LIPIcs.ICDT.2022.5}, annote = {Keywords: Database queries, linear programming, hypergraph decomposition} }
Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)
Austen Z. Fan and Paraschos Koutris. Certifiable Robustness for Nearest Neighbor Classifiers. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{fan_et_al:LIPIcs.ICDT.2022.6, author = {Fan, Austen Z. and Koutris, Paraschos}, title = {{Certifiable Robustness for Nearest Neighbor Classifiers}}, booktitle = {25th International Conference on Database Theory (ICDT 2022)}, pages = {6:1--6:20}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.6}, URN = {urn:nbn:de:0030-drops-158809}, doi = {10.4230/LIPIcs.ICDT.2022.6}, annote = {Keywords: Inconsistent databases, k-NN classification, certifiable robustness} }
Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)
Raghavendra Addanki, Andrew McGregor, Alexandra Meliou, and Zafeiria Moumoulidou. Improved Approximation and Scalability for Fair Max-Min Diversification. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{addanki_et_al:LIPIcs.ICDT.2022.7, author = {Addanki, Raghavendra and McGregor, Andrew and Meliou, Alexandra and Moumoulidou, Zafeiria}, title = {{Improved Approximation and Scalability for Fair Max-Min Diversification}}, booktitle = {25th International Conference on Database Theory (ICDT 2022)}, pages = {7:1--7: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.7}, URN = {urn:nbn:de:0030-drops-158812}, doi = {10.4230/LIPIcs.ICDT.2022.7}, annote = {Keywords: algorithmic fairness, diversity maximization, data selection, approximation algorithms} }
Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)
Gaetano Geck, Jens Keppeler, Thomas Schwentick, and Christopher Spinrath. Rewriting with Acyclic Queries: Mind Your Head. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{geck_et_al:LIPIcs.ICDT.2022.8, author = {Geck, Gaetano and Keppeler, Jens and Schwentick, Thomas and Spinrath, Christopher}, title = {{Rewriting with Acyclic Queries: Mind Your Head}}, booktitle = {25th International Conference on Database Theory (ICDT 2022)}, pages = {8:1--8:20}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.8}, URN = {urn:nbn:de:0030-drops-158829}, doi = {10.4230/LIPIcs.ICDT.2022.8}, annote = {Keywords: rewriting, acyclic rewriting, acyclic conjunctive queries, free-connex queries, hierarchical queries, NP-hardness} }
Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)
Yufei Tao. Parallel Acyclic Joins with Canonical Edge Covers. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{tao:LIPIcs.ICDT.2022.9, author = {Tao, Yufei}, title = {{Parallel Acyclic Joins with Canonical Edge Covers}}, booktitle = {25th International Conference on Database Theory (ICDT 2022)}, pages = {9:1--9:19}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.9}, URN = {urn:nbn:de:0030-drops-158838}, doi = {10.4230/LIPIcs.ICDT.2022.9}, annote = {Keywords: Joins, Conjunctive Queries, MPC Algorithms, Parallel Computing} }
Feedback for Dagstuhl Publishing