Published in: Dagstuhl Reports, Volume 13, Issue 5 (2023)
Gerth Stølting Brodal, John Iacono, László Kozma, Vijaya Ramachandran, and Justin Dallant. Scalable Data Structures (Dagstuhl Seminar 23211). In Dagstuhl Reports, Volume 13, Issue 5, pp. 114-135, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@Article{brodal_et_al:DagRep.13.5.114, author = {Brodal, Gerth St{\o}lting and Iacono, John and Kozma, L\'{a}szl\'{o} and Ramachandran, Vijaya and Dallant, Justin}, title = {{Scalable Data Structures (Dagstuhl Seminar 23211)}}, pages = {114--135}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2023}, volume = {13}, number = {5}, editor = {Brodal, Gerth St{\o}lting and Iacono, John and Kozma, L\'{a}szl\'{o} and Ramachandran, Vijaya and Dallant, Justin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.13.5.114}, URN = {urn:nbn:de:0030-drops-193676}, doi = {10.4230/DagRep.13.5.114}, annote = {Keywords: algorithms, big data, computational models, data structures, GPU computing, parallel computation} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Rathish Das, John Iacono, and Yakov Nekrich. External-Memory Dictionaries with Worst-Case Update Cost. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{das_et_al:LIPIcs.ISAAC.2022.21, author = {Das, Rathish and Iacono, John and Nekrich, Yakov}, title = {{External-Memory Dictionaries with Worst-Case Update Cost}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {21:1--21:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.21}, URN = {urn:nbn:de:0030-drops-173060}, doi = {10.4230/LIPIcs.ISAAC.2022.21}, annote = {Keywords: Data Structures, External Memory, Buffer Tree} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Justin Dallant and John Iacono. Conditional Lower Bounds for Dynamic Geometric Measure Problems. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 39:1-39:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{dallant_et_al:LIPIcs.ESA.2022.39, author = {Dallant, Justin and Iacono, John}, title = {{Conditional Lower Bounds for Dynamic Geometric Measure Problems}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {39:1--39:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.39}, URN = {urn:nbn:de:0030-drops-169777}, doi = {10.4230/LIPIcs.ESA.2022.39}, annote = {Keywords: Computational geometry, Fine-grained complexity, Dynamic data structures} }
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
Justin Dallant and John Iacono. How Fast Can We Play Tetris Greedily with Rectangular Pieces?. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{dallant_et_al:LIPIcs.FUN.2022.13, author = {Dallant, Justin and Iacono, John}, title = {{How Fast Can We Play Tetris Greedily with Rectangular Pieces?}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {13:1--13:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.13}, URN = {urn:nbn:de:0030-drops-159839}, doi = {10.4230/LIPIcs.FUN.2022.13}, annote = {Keywords: Tetris, Fine-grained complexity, Dynamic data structures, Axis-aligned rectangles} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John Iacono, and Micha Sharir. Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{aronov_et_al:LIPIcs.ISAAC.2021.3, author = {Aronov, Boris and de Berg, Mark and Cardinal, Jean and Ezra, Esther and Iacono, John and Sharir, Micha}, title = {{Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {3:1--3:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.3}, URN = {urn:nbn:de:0030-drops-154363}, doi = {10.4230/LIPIcs.ISAAC.2021.3}, annote = {Keywords: Computational geometry, Algebraic decision-tree model, Polynomial partitioning, Primal-dual range searching, Order types, Point location, Hierarchical partitions} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Jean Cardinal, Justin Dallant, and John Iacono. An Instance-Optimal Algorithm for Bichromatic Rectangular Visibility. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{cardinal_et_al:LIPIcs.ESA.2021.24, author = {Cardinal, Jean and Dallant, Justin and Iacono, John}, title = {{An Instance-Optimal Algorithm for Bichromatic Rectangular Visibility}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {24:1--24:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.24}, URN = {urn:nbn:de:0030-drops-146057}, doi = {10.4230/LIPIcs.ESA.2021.24}, annote = {Keywords: computational geometry, instance-optimality, colored point sets, empty rectangles, visibility} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Jean Cardinal, John Iacono, and Grigorios Koumoutsos. Worst-Case Efficient Dynamic Geometric Independent Set. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{cardinal_et_al:LIPIcs.ESA.2021.25, author = {Cardinal, Jean and Iacono, John and Koumoutsos, Grigorios}, title = {{Worst-Case Efficient Dynamic Geometric Independent Set}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {25:1--25:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.25}, URN = {urn:nbn:de:0030-drops-146061}, doi = {10.4230/LIPIcs.ESA.2021.25}, annote = {Keywords: Maximum independent set, deamortization, approximation} }
Published in: Dagstuhl Reports, Volume 11, Issue 1 (2021)
Gerth Stølting Brodal, John Iacono, Markus E. Nebel, and Vijaya Ramachandran. Scalable Data Structures (Dagstuhl Seminar 21071). In Dagstuhl Reports, Volume 11, Issue 1, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@Article{brodal_et_al:DagRep.11.1.1, author = {Brodal, Gerth St{\o}lting and Iacono, John and Nebel, Markus E. and Ramachandran, Vijaya}, title = {{Scalable Data Structures (Dagstuhl Seminar 21071)}}, pages = {1--23}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2021}, volume = {11}, number = {1}, editor = {Brodal, Gerth St{\o}lting and Iacono, John and Nebel, Markus E. and Ramachandran, Vijaya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.11.1.1}, URN = {urn:nbn:de:0030-drops-143481}, doi = {10.4230/DagRep.11.1.1}, annote = {Keywords: algorithms, big data, data structures, GPU computing, large data sets, models of computation, parallel algorithms} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
William Kuszmaul and Alek Westover. The Variable-Processor Cup Game. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{kuszmaul_et_al:LIPIcs.ITCS.2021.16, author = {Kuszmaul, William and Westover, Alek}, title = {{The Variable-Processor Cup Game}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {16:1--16:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.16}, URN = {urn:nbn:de:0030-drops-135559}, doi = {10.4230/LIPIcs.ITCS.2021.16}, annote = {Keywords: scheduling, cup games, online algorithms, lower bounds} }
Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Jean Cardinal and Aurélien Ooms. Sparse Regression via Range Counting. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{cardinal_et_al:LIPIcs.SWAT.2020.20, author = {Cardinal, Jean and Ooms, Aur\'{e}lien}, title = {{Sparse Regression via Range Counting}}, booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)}, pages = {20:1--20:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-150-4}, ISSN = {1868-8969}, year = {2020}, volume = {162}, editor = {Albers, Susanne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.20}, URN = {urn:nbn:de:0030-drops-122677}, doi = {10.4230/LIPIcs.SWAT.2020.20}, annote = {Keywords: Sparse Linear Regression, Orthogonal Range Searching, Affine Degeneracy Testing, Nearest Neighbors, Hyperplane Arrangements} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Boris Aronov, Esther Ezra, and Micha Sharir. Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{aronov_et_al:LIPIcs.SoCG.2020.8, author = {Aronov, Boris and Ezra, Esther and Sharir, Micha}, title = {{Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {8:1--8:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-143-6}, ISSN = {1868-8969}, year = {2020}, volume = {164}, editor = {Cabello, Sergio and Chen, Danny Z.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.8}, URN = {urn:nbn:de:0030-drops-121666}, doi = {10.4230/LIPIcs.SoCG.2020.8}, annote = {Keywords: Algebraic decision tree, Polynomial partition, Collinearity testing, 3SUM-hard problems, Polynomials vanishing on Cartesian products} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
John Iacono, Ben Karsin, and Grigorios Koumoutsos. External Memory Planar Point Location with Fast Updates. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 58:1-58:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{iacono_et_al:LIPIcs.ISAAC.2019.58, author = {Iacono, John and Karsin, Ben and Koumoutsos, Grigorios}, title = {{External Memory Planar Point Location with Fast Updates}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {58:1--58:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.58}, URN = {urn:nbn:de:0030-drops-115548}, doi = {10.4230/LIPIcs.ISAAC.2019.58}, annote = {Keywords: point location, data structures, dynamic algorithms, computational geometry} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
John Iacono, Riko Jacob, and Konstantinos Tsakalidis. External Memory Priority Queues with Decrease-Key and Applications to Graph Algorithms. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 60:1-60:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{iacono_et_al:LIPIcs.ESA.2019.60, author = {Iacono, John and Jacob, Riko and Tsakalidis, Konstantinos}, title = {{External Memory Priority Queues with Decrease-Key and Applications to Graph Algorithms}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {60:1--60:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.60}, URN = {urn:nbn:de:0030-drops-111817}, doi = {10.4230/LIPIcs.ESA.2019.60}, annote = {Keywords: priority queues, external memory, graph algorithms, shortest paths, depth-first search, breadth-first search} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Mordecai Golin, John Iacono, Stefan Langerman, J. Ian Munro, and Yakov Nekrich. Dynamic Trees with Almost-Optimal Access Cost. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{golin_et_al:LIPIcs.ESA.2018.38, author = {Golin, Mordecai and Iacono, John and Langerman, Stefan and Munro, J. Ian and Nekrich, Yakov}, title = {{Dynamic Trees with Almost-Optimal Access Cost}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {38:1--38:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.38}, URN = {urn:nbn:de:0030-drops-95017}, doi = {10.4230/LIPIcs.ESA.2018.38}, annote = {Keywords: Data Structures, Binary Search Trees, Adaptive Alphabetic Coding} }
Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)
Jean Cardinal, Timothy M. Chan, John Iacono, Stefan Langerman, and Aurélien Ooms. Subquadratic Encodings for Point Configurations. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{cardinal_et_al:LIPIcs.SoCG.2018.20, author = {Cardinal, Jean and Chan, Timothy M. and Iacono, John and Langerman, Stefan and Ooms, Aur\'{e}lien}, title = {{Subquadratic Encodings for Point Configurations}}, booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)}, pages = {20:1--20:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-066-8}, ISSN = {1868-8969}, year = {2018}, volume = {99}, editor = {Speckmann, Bettina and T\'{o}th, Csaba D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.20}, URN = {urn:nbn:de:0030-drops-87337}, doi = {10.4230/LIPIcs.SoCG.2018.20}, annote = {Keywords: point configuration, order type, chirotope, succinct data structure} }
Feedback for Dagstuhl Publishing