Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)
Alkida Balliu, Pierre Fraigniaud, Patrick Lambein-Monette, Dennis Olivetti, and Mikaël Rabie. Asynchronous Fault-Tolerant Distributed Proper Coloring of Graphs. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{balliu_et_al:LIPIcs.DISC.2024.5, author = {Balliu, Alkida and Fraigniaud, Pierre and Lambein-Monette, Patrick and Olivetti, Dennis and Rabie, Mika\"{e}l}, title = {{Asynchronous Fault-Tolerant Distributed Proper Coloring of Graphs}}, booktitle = {38th International Symposium on Distributed Computing (DISC 2024)}, pages = {5:1--5:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-352-2}, ISSN = {1868-8969}, year = {2024}, volume = {319}, editor = {Alistarh, Dan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.5}, URN = {urn:nbn:de:0030-drops-212328}, doi = {10.4230/LIPIcs.DISC.2024.5}, annote = {Keywords: LOCAL model, Graph Coloring, Renaming, Weak Symmetry-Breaking, Fault-Tolerance, Wait-Free Computing} }
Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)
Yannis Coutouly and Emmanuel Godard. A Simple Computability Theorem for Colorless Tasks in Submodels of the Iterated Immediate Snapshot. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 16:1-16:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{coutouly_et_al:LIPIcs.DISC.2024.16, author = {Coutouly, Yannis and Godard, Emmanuel}, title = {{A Simple Computability Theorem for Colorless Tasks in Submodels of the Iterated Immediate Snapshot}}, booktitle = {38th International Symposium on Distributed Computing (DISC 2024)}, pages = {16:1--16:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-352-2}, ISSN = {1868-8969}, year = {2024}, volume = {319}, editor = {Alistarh, Dan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.16}, URN = {urn:nbn:de:0030-drops-212422}, doi = {10.4230/LIPIcs.DISC.2024.16}, annote = {Keywords: topological methods, geometric simplicial complex, set-agreement} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Mikkel Abrahamsen, Ioana O. Bercea, Lorenzo Beretta, Jonas Klausen, and László Kozma. Online Sorting and Online TSP: Randomized, Stochastic, and High-Dimensional. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{abrahamsen_et_al:LIPIcs.ESA.2024.5, author = {Abrahamsen, Mikkel and Bercea, Ioana O. and Beretta, Lorenzo and Klausen, Jonas and Kozma, L\'{a}szl\'{o}}, title = {{Online Sorting and Online TSP: Randomized, Stochastic, and High-Dimensional}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {5:1--5:15}, 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.5}, URN = {urn:nbn:de:0030-drops-210766}, doi = {10.4230/LIPIcs.ESA.2024.5}, annote = {Keywords: sorting, online algorithm, TSP} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao, Christoph Grunau, Bernhard Haeupler, Yonggang Jiang, Danupon Nanongkai, and Hsin-Hao Su. Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{ashvinkumar_et_al:LIPIcs.ESA.2024.13, author = {Ashvinkumar, Vikrant and Bernstein, Aaron and Cao, Nairen and Grunau, Christoph and Haeupler, Bernhard and Jiang, Yonggang and Nanongkai, Danupon and Su, Hsin-Hao}, title = {{Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {13:1--13:15}, 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.13}, URN = {urn:nbn:de:0030-drops-210849}, doi = {10.4230/LIPIcs.ESA.2024.13}, annote = {Keywords: Parallel algorithm, distributed algorithm, shortest paths} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Shimon Kogan and Merav Parter. The Algorithmic Power of the Greene-Kleitman Theorem. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 80:1-80:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kogan_et_al:LIPIcs.ESA.2024.80, author = {Kogan, Shimon and Parter, Merav}, title = {{The Algorithmic Power of the Greene-Kleitman Theorem}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {80:1--80:14}, 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.80}, URN = {urn:nbn:de:0030-drops-211512}, doi = {10.4230/LIPIcs.ESA.2024.80}, annote = {Keywords: Chains, Antichains, DAG} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Slobodan Mitrović, Ronitt Rubinfeld, and Mihir Singhal. Locally Computing Edge Orientations. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 89:1-89:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mitrovic_et_al:LIPIcs.ESA.2024.89, author = {Mitrovi\'{c}, Slobodan and Rubinfeld, Ronitt and Singhal, Mihir}, title = {{Locally Computing Edge Orientations}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {89:1--89: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.89}, URN = {urn:nbn:de:0030-drops-211603}, doi = {10.4230/LIPIcs.ESA.2024.89}, annote = {Keywords: local computation algorithms, edge orientation, tree coloring} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Hadley Black. Nearly Optimal Bounds for Sample-Based Testing and Learning of k-Monotone Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 37:1-37:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{black:LIPIcs.APPROX/RANDOM.2024.37, author = {Black, Hadley}, title = {{Nearly Optimal Bounds for Sample-Based Testing and Learning of k-Monotone Functions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {37:1--37:23}, 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.37}, URN = {urn:nbn:de:0030-drops-210308}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.37}, annote = {Keywords: Property testing, learning, Boolean functions, monotonicity, k-monotonicity} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Halley Goldberg and Valentine Kabanets. Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 51:1-51:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{goldberg_et_al:LIPIcs.APPROX/RANDOM.2024.51, author = {Goldberg, Halley and Kabanets, Valentine}, title = {{Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {51:1--51:19}, 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.51}, URN = {urn:nbn:de:0030-drops-210444}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.51}, annote = {Keywords: Meta-complexity, Randomized reductions, NP-hardness, Worst-case complexity, Time-bounded Kolmogorov complexity} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Nikhil S. Mande, Manaswi Paraashar, Swagato Sanyal, and Nitin Saurabh. On the Communication Complexity of Finding a King in a Tournament. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 64:1-64:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mande_et_al:LIPIcs.APPROX/RANDOM.2024.64, author = {Mande, Nikhil S. and Paraashar, Manaswi and Sanyal, Swagato and Saurabh, Nitin}, title = {{On the Communication Complexity of Finding a King in a Tournament}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {64:1--64:23}, 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.64}, URN = {urn:nbn:de:0030-drops-210571}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.64}, annote = {Keywords: Communication complexity, tournaments, query complexity} }
Published in: LIPIcs, Volume 316, 6th Conference on Advances in Financial Technologies (AFT 2024)
Aggelos Kiayias, Elias Koutsoupias, Philip Lazos, and Giorgos Panagiotakos. Blockchain Space Tokenization. In 6th Conference on Advances in Financial Technologies (AFT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 316, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kiayias_et_al:LIPIcs.AFT.2024.9, author = {Kiayias, Aggelos and Koutsoupias, Elias and Lazos, Philip and Panagiotakos, Giorgos}, title = {{Blockchain Space Tokenization}}, booktitle = {6th Conference on Advances in Financial Technologies (AFT 2024)}, pages = {9:1--9:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-345-4}, ISSN = {1868-8969}, year = {2024}, volume = {316}, editor = {B\"{o}hme, Rainer and Kiffer, Lucianna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2024.9}, URN = {urn:nbn:de:0030-drops-209453}, doi = {10.4230/LIPIcs.AFT.2024.9}, annote = {Keywords: Blockchain protocols, Predictable Service, Transaction Fees} }
Published in: LIPIcs, Volume 310, 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024)
Aleksandrs Belovs. A Direct Reduction from the Polynomial to the Adversary Method. In 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 310, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{belovs:LIPIcs.TQC.2024.11, author = {Belovs, Aleksandrs}, title = {{A Direct Reduction from the Polynomial to the Adversary Method}}, booktitle = {19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024)}, pages = {11:1--11:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-328-7}, ISSN = {1868-8969}, year = {2024}, volume = {310}, editor = {Magniez, Fr\'{e}d\'{e}ric and Grilo, Alex Bredariol}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2024.11}, URN = {urn:nbn:de:0030-drops-206814}, doi = {10.4230/LIPIcs.TQC.2024.11}, annote = {Keywords: Polynomials, Quantum Adversary Bound} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Bartłomiej Bosek, Grzegorz Gutowski, Michał Lasoń, and Jakub Przybyło. First-Fit Coloring of Forests in Random Arrival Model. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 33:1-33:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bosek_et_al:LIPIcs.MFCS.2024.33, author = {Bosek, Bart{\l}omiej and Gutowski, Grzegorz and Laso\'{n}, Micha{\l} and Przyby{\l}o, Jakub}, title = {{First-Fit Coloring of Forests in Random Arrival Model}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {33:1--33:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.33}, URN = {urn:nbn:de:0030-drops-205892}, doi = {10.4230/LIPIcs.MFCS.2024.33}, annote = {Keywords: First-Fit, Online Algorithms, Graph Coloring, Random Arrival Model} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Samir Datta, Asif Khan, Anish Mukherjee, Felix Tschirbs, Nils Vortmeier, and Thomas Zeume. Query Maintenance Under Batch Changes with Small-Depth Circuits. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 46:1-46:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{datta_et_al:LIPIcs.MFCS.2024.46, author = {Datta, Samir and Khan, Asif and Mukherjee, Anish and Tschirbs, Felix and Vortmeier, Nils and Zeume, Thomas}, title = {{Query Maintenance Under Batch Changes with Small-Depth Circuits}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {46:1--46:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.46}, URN = {urn:nbn:de:0030-drops-206027}, doi = {10.4230/LIPIcs.MFCS.2024.46}, annote = {Keywords: Dynamic complexity theory, parallel computation, dynamic algorithms} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
William M. Hoza. A Technique for Hardness Amplification Against AC⁰. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hoza:LIPIcs.CCC.2024.1, author = {Hoza, William M.}, title = {{A Technique for Hardness Amplification Against AC⁰}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {1:1--1:20}, 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.1}, URN = {urn:nbn:de:0030-drops-203977}, doi = {10.4230/LIPIcs.CCC.2024.1}, annote = {Keywords: Bounded-depth circuits, average-case lower bounds, hardness amplification, XOR lemmas} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Edward Pyne. Derandomizing Logspace with a Small Shared Hard Drive. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{pyne:LIPIcs.CCC.2024.4, author = {Pyne, Edward}, title = {{Derandomizing Logspace with a Small Shared Hard Drive}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {4:1--4:20}, 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.4}, URN = {urn:nbn:de:0030-drops-204006}, doi = {10.4230/LIPIcs.CCC.2024.4}, annote = {Keywords: Catalytic computation, space-bounded computation, derandomization} }
Feedback for Dagstuhl Publishing