OASIcs, Volume 75
ATMOS 2019, September 12-13, 2019, Munich, Germany
Editors: Valentina Cacchiani and Alberto Marchetti-Spaccamela
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Nils Fleischhacker, Kasper Green Larsen, Maciej Obremski, and Mark Simkin. Invertible Bloom Lookup Tables with Less Memory and Randomness. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{fleischhacker_et_al:LIPIcs.ESA.2024.54, author = {Fleischhacker, Nils and Larsen, Kasper Green and Obremski, Maciej and Simkin, Mark}, title = {{Invertible Bloom Lookup Tables with Less Memory and Randomness}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {54:1--54:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.54}, URN = {urn:nbn:de:0030-drops-211252}, doi = {10.4230/LIPIcs.ESA.2024.54}, annote = {Keywords: Invertible Bloom Lookup Tables} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Mohit Garg, Debajyoti Kar, and Arindam Khan. Random-Order Online Independent Set of Intervals and Hyperrectangles. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 58:1-58:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{garg_et_al:LIPIcs.ESA.2024.58, author = {Garg, Mohit and Kar, Debajyoti and Khan, Arindam}, title = {{Random-Order Online Independent Set of Intervals and Hyperrectangles}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {58:1--58:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.58}, URN = {urn:nbn:de:0030-drops-211298}, doi = {10.4230/LIPIcs.ESA.2024.58}, annote = {Keywords: Online Algorithms, Random-Order Model, Maximum Independent Set of Rectangles, Hyperrectangles, Fat Objects, Interval Scheduling} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Shuchi Chawla and Dimitris Christou. Online Time-Windows TSP with Predictions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 2:1-2:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chawla_et_al:LIPIcs.APPROX/RANDOM.2024.2, author = {Chawla, Shuchi and Christou, Dimitris}, title = {{Online Time-Windows TSP with Predictions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {2:1--2:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.2}, URN = {urn:nbn:de:0030-drops-209954}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.2}, annote = {Keywords: Travelling Salesman Problem, Predictions, Learning-Augmented Algorithms, Approximation} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Josef Minařík and Jiří Sgall. Speed-Robust Scheduling Revisited. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{minarik_et_al:LIPIcs.APPROX/RANDOM.2024.8, author = {Mina\v{r}{\'\i}k, Josef and Sgall, Ji\v{r}{\'\i}}, title = {{Speed-Robust Scheduling Revisited}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {8:1--8:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.8}, URN = {urn:nbn:de:0030-drops-210010}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.8}, annote = {Keywords: scheduling, approximation algorithms, makespan, uniform speeds} }
Published in: LIPIcs, Volume 311, 35th International Conference on Concurrency Theory (CONCUR 2024)
Thomas A. Henzinger, Nicolas Mazzocchi, and N. Ege Saraç. Strategic Dominance: A New Preorder for Nondeterministic Processes. In 35th International Conference on Concurrency Theory (CONCUR 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 311, pp. 29:1-29:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{henzinger_et_al:LIPIcs.CONCUR.2024.29, author = {Henzinger, Thomas A. and Mazzocchi, Nicolas and Sara\c{c}, N. Ege}, title = {{Strategic Dominance: A New Preorder for Nondeterministic Processes}}, booktitle = {35th International Conference on Concurrency Theory (CONCUR 2024)}, pages = {29:1--29:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-339-3}, ISSN = {1868-8969}, year = {2024}, volume = {311}, editor = {Majumdar, Rupak and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2024.29}, URN = {urn:nbn:de:0030-drops-208011}, doi = {10.4230/LIPIcs.CONCUR.2024.29}, annote = {Keywords: quantitative automata, refinement relation, resolver, strategy, history-determinism} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Graham Cormode, Marcel Dall'Agnol, Tom Gur, and Chris Hickey. Streaming Zero-Knowledge Proofs. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 2:1-2:66, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{cormode_et_al:LIPIcs.CCC.2024.2, author = {Cormode, Graham and Dall'Agnol, Marcel and Gur, Tom and Hickey, Chris}, title = {{Streaming Zero-Knowledge Proofs}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {2:1--2:66}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.2}, URN = {urn:nbn:de:0030-drops-203988}, doi = {10.4230/LIPIcs.CCC.2024.2}, annote = {Keywords: Zero-knowledge proofs, streaming algorithms, computational complexity} }
Published in: LIPIcs, Volume 299, 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)
Beniamino Accattoli and Claudio Sacerdoti Coen. IMELL Cut Elimination with Linear Overhead. In 9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 299, pp. 24:1-24:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{accattoli_et_al:LIPIcs.FSCD.2024.24, author = {Accattoli, Beniamino and Sacerdoti Coen, Claudio}, title = {{IMELL Cut Elimination with Linear Overhead}}, booktitle = {9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024)}, pages = {24:1--24:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-323-2}, ISSN = {1868-8969}, year = {2024}, volume = {299}, editor = {Rehof, Jakob}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2024.24}, URN = {urn:nbn:de:0030-drops-203539}, doi = {10.4230/LIPIcs.FSCD.2024.24}, annote = {Keywords: Lambda calculus, linear logic, abstract machines} }
Published in: LIPIcs, Volume 298, 36th Euromicro Conference on Real-Time Systems (ECRTS 2024)
Pourya Gohari, Jeroen Voeten, and Mitra Nasri. Reachability-Based Response-Time Analysis of Preemptive Tasks Under Global Scheduling. In 36th Euromicro Conference on Real-Time Systems (ECRTS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 298, pp. 3:1-3:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{gohari_et_al:LIPIcs.ECRTS.2024.3, author = {Gohari, Pourya and Voeten, Jeroen and Nasri, Mitra}, title = {{Reachability-Based Response-Time Analysis of Preemptive Tasks Under Global Scheduling}}, booktitle = {36th Euromicro Conference on Real-Time Systems (ECRTS 2024)}, pages = {3:1--3:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-324-9}, ISSN = {1868-8969}, year = {2024}, volume = {298}, editor = {Pellizzoni, Rodolfo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2024.3}, URN = {urn:nbn:de:0030-drops-203064}, doi = {10.4230/LIPIcs.ECRTS.2024.3}, annote = {Keywords: Response-time analysis, global scheduling, preemptive, job-level fixed-priority scheduling policy, multicore, schedule-abstraction graph} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Keren Censor-Hillel, Tomer Even, and Virginia Vassilevska Williams. Fast Approximate Counting of Cycles. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{censorhillel_et_al:LIPIcs.ICALP.2024.37, author = {Censor-Hillel, Keren and Even, Tomer and Vassilevska Williams, Virginia}, title = {{Fast Approximate Counting of Cycles}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {37:1--37: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.37}, URN = {urn:nbn:de:0030-drops-201809}, doi = {10.4230/LIPIcs.ICALP.2024.37}, annote = {Keywords: Approximate triangle counting, Approximate cycle counting Fast matrix multiplication, Fast rectangular matrix multiplication} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yu Chen, Michael Kapralov, Mikhail Makarov, and Davide Mazzali. On the Streaming Complexity of Expander Decomposition. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chen_et_al:LIPIcs.ICALP.2024.46, author = {Chen, Yu and Kapralov, Michael and Makarov, Mikhail and Mazzali, Davide}, title = {{On the Streaming Complexity of Expander Decomposition}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {46:1--46: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.46}, URN = {urn:nbn:de:0030-drops-201890}, doi = {10.4230/LIPIcs.ICALP.2024.46}, annote = {Keywords: Graph Sketching, Dynamic Streaming, Expander Decomposition} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Cella Florescu, Rasmus Kyng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Optimal Electrical Oblivious Routing on Expanders. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 65:1-65:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{florescu_et_al:LIPIcs.ICALP.2024.65, author = {Florescu, Cella and Kyng, Rasmus and Gutenberg, Maximilian Probst and Sachdeva, Sushant}, title = {{Optimal Electrical Oblivious Routing on Expanders}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {65:1--65:19}, 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.65}, URN = {urn:nbn:de:0030-drops-202083}, doi = {10.4230/LIPIcs.ICALP.2024.65}, annote = {Keywords: Expanders, Oblivious routing for 𝓁\underlinep, Electrical flow routing} }
Published in: LIPIcs, Volume 262, 35th Euromicro Conference on Real-Time Systems (ECRTS 2023)
Kunal Agrawal, Sanjoy Baruah, Michael A. Bender, and Alberto Marchetti-Spaccamela. The Safe and Effective Use of Low-Assurance Predictions in Safety-Critical Systems. In 35th Euromicro Conference on Real-Time Systems (ECRTS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 262, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{agrawal_et_al:LIPIcs.ECRTS.2023.3, author = {Agrawal, Kunal and Baruah, Sanjoy and Bender, Michael A. and Marchetti-Spaccamela, Alberto}, title = {{The Safe and Effective Use of Low-Assurance Predictions in Safety-Critical Systems}}, booktitle = {35th Euromicro Conference on Real-Time Systems (ECRTS 2023)}, pages = {3:1--3:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-280-8}, ISSN = {1868-8969}, year = {2023}, volume = {262}, editor = {Papadopoulos, Alessandro V.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2023.3}, URN = {urn:nbn:de:0030-drops-180323}, doi = {10.4230/LIPIcs.ECRTS.2023.3}, annote = {Keywords: Algorithms using predictions, robust scheduling, energy minimization, classification, on-line scheduling} }
Published in: LIPIcs, Volume 196, 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)
Sanjoy Baruah and Alberto Marchetti-Spaccamela. Feasibility Analysis of Conditional DAG Tasks. In 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 196, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{baruah_et_al:LIPIcs.ECRTS.2021.12, author = {Baruah, Sanjoy and Marchetti-Spaccamela, Alberto}, title = {{Feasibility Analysis of Conditional DAG Tasks}}, booktitle = {33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)}, pages = {12:1--12:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-192-4}, ISSN = {1868-8969}, year = {2021}, volume = {196}, editor = {Brandenburg, Bj\"{o}rn B.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2021.12}, URN = {urn:nbn:de:0030-drops-139433}, doi = {10.4230/LIPIcs.ECRTS.2021.12}, annote = {Keywords: Multiprocessor feasibility analysis, Conditional Directed Acyclic Graphs, PSPACE-complete} }
Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
Giulia Bernardini, Alberto Marchetti-Spaccamela, Solon P. Pissis, Leen Stougie, and Michelle Sweering. Constructing Strings Avoiding Forbidden Substrings. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bernardini_et_al:LIPIcs.CPM.2021.9, author = {Bernardini, Giulia and Marchetti-Spaccamela, Alberto and Pissis, Solon P. and Stougie, Leen and Sweering, Michelle}, title = {{Constructing Strings Avoiding Forbidden Substrings}}, booktitle = {32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)}, pages = {9:1--9:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-186-3}, ISSN = {1868-8969}, year = {2021}, volume = {191}, editor = {Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.9}, URN = {urn:nbn:de:0030-drops-139604}, doi = {10.4230/LIPIcs.CPM.2021.9}, annote = {Keywords: string algorithms, forbidden strings, de Bruijn graphs, data sanitization} }
Feedback for Dagstuhl Publishing