Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)
Uri Meir and Ami Paz. Smoothed Analysis of Dynamic Graph Algorithms. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 102:1-102:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)
@InProceedings{meir_et_al:LIPIcs.ITCS.2026.102,
author = {Meir, Uri and Paz, Ami},
title = {{Smoothed Analysis of Dynamic Graph Algorithms}},
booktitle = {17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
pages = {102:1--102:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-410-9},
ISSN = {1868-8969},
year = {2026},
volume = {362},
editor = {Saraf, Shubhangi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.102},
URN = {urn:nbn:de:0030-drops-253896},
doi = {10.4230/LIPIcs.ITCS.2026.102},
annote = {Keywords: Dynamic graph algorithms, Smoothed analysis, Shortest paths}
}
Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)
Conor Power, Paraschos Koutris, and Joseph M. Hellerstein. The Free Termination Property of Queries over Time. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 32:1-32:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{power_et_al:LIPIcs.ICDT.2025.32,
author = {Power, Conor and Koutris, Paraschos and Hellerstein, Joseph M.},
title = {{The Free Termination Property of Queries over Time}},
booktitle = {28th International Conference on Database Theory (ICDT 2025)},
pages = {32:1--32:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-364-5},
ISSN = {1868-8969},
year = {2025},
volume = {328},
editor = {Roy, Sudeepa and Kara, Ahmet},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.32},
URN = {urn:nbn:de:0030-drops-229736},
doi = {10.4230/LIPIcs.ICDT.2025.32},
annote = {Keywords: distributed systems, algebraic data models, coordination-free systems}
}
Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)
Paraschos Koutris. Generalized Covers for Conjunctive Queries. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{koutris:LIPIcs.ICDT.2025.28,
author = {Koutris, Paraschos},
title = {{Generalized Covers for Conjunctive Queries}},
booktitle = {28th International Conference on Database Theory (ICDT 2025)},
pages = {28:1--28:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-364-5},
ISSN = {1868-8969},
year = {2025},
volume = {328},
editor = {Roy, Sudeepa and Kara, Ahmet},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.28},
URN = {urn:nbn:de:0030-drops-229698},
doi = {10.4230/LIPIcs.ICDT.2025.28},
annote = {Keywords: Conjunctive Query, tree decomposition, cover}
}
Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)
Benny Kimelfeld, Wim Martens, and Matthias Niewerth. A Formal Language Perspective on Factorized Representations. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{kimelfeld_et_al:LIPIcs.ICDT.2025.20,
author = {Kimelfeld, Benny and Martens, Wim and Niewerth, Matthias},
title = {{A Formal Language Perspective on Factorized Representations}},
booktitle = {28th International Conference on Database Theory (ICDT 2025)},
pages = {20:1--20:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-364-5},
ISSN = {1868-8969},
year = {2025},
volume = {328},
editor = {Roy, Sudeepa and Kara, Ahmet},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.20},
URN = {urn:nbn:de:0030-drops-229614},
doi = {10.4230/LIPIcs.ICDT.2025.20},
annote = {Keywords: Databases, relational databases, graph databases, factorized databases, regular path queries, compact representations}
}
Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)
Ahmet Kara, Zheng Luo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Tractable Conjunctive Queries over Static and Dynamic Relations. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 12:1-12:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{kara_et_al:LIPIcs.ICDT.2025.12,
author = {Kara, Ahmet and Luo, Zheng and Nikolic, Milos and Olteanu, Dan and Zhang, Haozhe},
title = {{Tractable Conjunctive Queries over Static and Dynamic Relations}},
booktitle = {28th International Conference on Database Theory (ICDT 2025)},
pages = {12:1--12:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-364-5},
ISSN = {1868-8969},
year = {2025},
volume = {328},
editor = {Roy, Sudeepa and Kara, Ahmet},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.12},
URN = {urn:nbn:de:0030-drops-229534},
doi = {10.4230/LIPIcs.ICDT.2025.12},
annote = {Keywords: fully dynamic algorithm, constant enumeration delay, constant update time}
}
Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)
Paraschos Koutris, Shaleen Deep, Austen Fan, and Hangdong Zhao. The Quest for Faster Join Algorithms (Invited Talk). In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 1:1-1:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{koutris_et_al:LIPIcs.ICDT.2025.1,
author = {Koutris, Paraschos and Deep, Shaleen and Fan, Austen and Zhao, Hangdong},
title = {{The Quest for Faster Join Algorithms}},
booktitle = {28th International Conference on Database Theory (ICDT 2025)},
pages = {1:1--1:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-364-5},
ISSN = {1868-8969},
year = {2025},
volume = {328},
editor = {Roy, Sudeepa and Kara, Ahmet},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.1},
URN = {urn:nbn:de:0030-drops-229428},
doi = {10.4230/LIPIcs.ICDT.2025.1},
annote = {Keywords: Conjunctive Queries, Joins, Tree Decompositions, Enumeration, Semirings}
}
Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)
Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Conjunctive Queries with Free Access Patterns Under Updates. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{kara_et_al:LIPIcs.ICDT.2023.17,
author = {Kara, Ahmet and Nikolic, Milos and Olteanu, Dan and Zhang, Haozhe},
title = {{Conjunctive Queries with Free Access Patterns Under Updates}},
booktitle = {26th International Conference on Database Theory (ICDT 2023)},
pages = {17:1--17:20},
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.17},
URN = {urn:nbn:de:0030-drops-177599},
doi = {10.4230/LIPIcs.ICDT.2023.17},
annote = {Keywords: fully dynamic algorithm, enumeration delay, complexity trade-off, dichotomy}
}
Published in: LIPIcs, Volume 252, 31st EACSL Annual Conference on Computer Science Logic (CSL 2023)
Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Evaluation Trade-Offs for Acyclic Conjunctive Queries. In 31st EACSL Annual Conference on Computer Science Logic (CSL 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 252, pp. 29:1-29:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{kara_et_al:LIPIcs.CSL.2023.29,
author = {Kara, Ahmet and Nikolic, Milos and Olteanu, Dan and Zhang, Haozhe},
title = {{Evaluation Trade-Offs for Acyclic Conjunctive Queries}},
booktitle = {31st EACSL Annual Conference on Computer Science Logic (CSL 2023)},
pages = {29:1--29:20},
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.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2023.29},
URN = {urn:nbn:de:0030-drops-174907},
doi = {10.4230/LIPIcs.CSL.2023.29},
annote = {Keywords: acyclic queries, query evaluation, enumeration delay}
}
Published in: LIPIcs, Volume 127, 22nd International Conference on Database Theory (ICDT 2019)
Ahmet Kara, Hung Q. Ngo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Counting Triangles under Updates in Worst-Case Optimal Time. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kara_et_al:LIPIcs.ICDT.2019.4,
author = {Kara, Ahmet and Ngo, Hung Q. and Nikolic, Milos and Olteanu, Dan and Zhang, Haozhe},
title = {{Counting Triangles under Updates in Worst-Case Optimal Time}},
booktitle = {22nd International Conference on Database Theory (ICDT 2019)},
pages = {4:1--4:18},
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.4},
URN = {urn:nbn:de:0030-drops-103068},
doi = {10.4230/LIPIcs.ICDT.2019.4},
annote = {Keywords: incremental view maintenance, amortized analysis, data skew}
}