Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, and Sagnik Mukhopadhyay. Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{assadi_et_al:LIPIcs.CCC.2024.7, author = {Assadi, Sepehr and Ghosh, Prantar and Loff, Bruno and Mittal, Parth and Mukhopadhyay, Sagnik}, title = {{Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {7:1--7:16}, 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.7}, URN = {urn:nbn:de:0030-drops-204035}, doi = {10.4230/LIPIcs.CCC.2024.7}, annote = {Keywords: Graph streaming, Lower bounds, Communication complexity, k-Cores and degeneracy} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yossi Azar, Shahar Lewkowicz, and Danny Vainstein. List Update with Delays or Time Windows. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 15:1-15:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{azar_et_al:LIPIcs.ICALP.2024.15, author = {Azar, Yossi and Lewkowicz, Shahar and Vainstein, Danny}, title = {{List Update with Delays or Time Windows}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {15:1--15: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.15}, URN = {urn:nbn:de:0030-drops-201583}, doi = {10.4230/LIPIcs.ICALP.2024.15}, annote = {Keywords: Online, List Update, Delay, Time Window, Deadline} }
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)
Andrei Constantinescu, Pascal Lenzner, Rebecca Reiffenhäuser, Daniel Schmand, and Giovanna Varricchio. Solving Woeginger’s Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 48:1-48:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{constantinescu_et_al:LIPIcs.ICALP.2024.48, author = {Constantinescu, Andrei and Lenzner, Pascal and Reiffenh\"{a}user, Rebecca and Schmand, Daniel and Varricchio, Giovanna}, title = {{Solving Woeginger’s Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {48:1--48:18}, 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.48}, URN = {urn:nbn:de:0030-drops-201910}, doi = {10.4230/LIPIcs.ICALP.2024.48}, annote = {Keywords: Algorithmic Game Theory, Dynamic Programming, Anonymous Hedonic Games, Single-Peaked Preferences, Social Optimum, Wonderful Partitions} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Esther Galby, Sándor Kisfaludi-Bak, Dániel Marx, and Roohani Sharma. Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 67:1-67:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{galby_et_al:LIPIcs.ICALP.2024.67, author = {Galby, Esther and Kisfaludi-Bak, S\'{a}ndor and Marx, D\'{a}niel and Sharma, Roohani}, title = {{Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {67:1--67: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.67}, URN = {urn:nbn:de:0030-drops-202104}, doi = {10.4230/LIPIcs.ICALP.2024.67}, annote = {Keywords: Directed Steiner Network, Sub-exponential algorithm} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Augusto Modanese and Yuichi Yoshida. Testing Spreading Behavior in Networks with Arbitrary Topologies. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 112:1-112:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{modanese_et_al:LIPIcs.ICALP.2024.112, author = {Modanese, Augusto and Yoshida, Yuichi}, title = {{Testing Spreading Behavior in Networks with Arbitrary Topologies}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {112:1--112: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.112}, URN = {urn:nbn:de:0030-drops-202554}, doi = {10.4230/LIPIcs.ICALP.2024.112}, annote = {Keywords: Property testing, bootstrap percolation, local phenomena, expander graphs} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Arnaud Carayol and Lucien Charamond. The Structure of Trees in the Pushdown Hierarchy. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 131:1-131:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{carayol_et_al:LIPIcs.ICALP.2024.131, author = {Carayol, Arnaud and Charamond, Lucien}, title = {{The Structure of Trees in the Pushdown Hierarchy}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {131:1--131:18}, 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.131}, URN = {urn:nbn:de:0030-drops-202749}, doi = {10.4230/LIPIcs.ICALP.2024.131}, annote = {Keywords: Pushdown hierarchy, Monadic second-order logic, Automatic numbers} }
Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)
Judith Beestermöller, Costas Busch, and Roger Wattenhofer. Fault-Tolerant Distributed Directories. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{beestermoller_et_al:LIPIcs.SAND.2024.5, author = {Beesterm\"{o}ller, Judith and Busch, Costas and Wattenhofer, Roger}, title = {{Fault-Tolerant Distributed Directories}}, booktitle = {3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)}, pages = {5:1--5:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-315-7}, ISSN = {1868-8969}, year = {2024}, volume = {292}, editor = {Casteigts, Arnaud and Kuhn, Fabian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.5}, URN = {urn:nbn:de:0030-drops-198833}, doi = {10.4230/LIPIcs.SAND.2024.5}, annote = {Keywords: distributed directory, sparse partition, fault tolerance, message complexity, path dilation} }
Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)
Roger Wattenhofer. Distributed Algorithms as a Gateway To Deductive Learning (Invited Talk). In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{wattenhofer:LIPIcs.OPODIS.2023.3, author = {Wattenhofer, Roger}, title = {{Distributed Algorithms as a Gateway To Deductive Learning}}, booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)}, pages = {3:1--3:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-308-9}, ISSN = {1868-8969}, year = {2024}, volume = {286}, editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.3}, URN = {urn:nbn:de:0030-drops-194936}, doi = {10.4230/LIPIcs.OPODIS.2023.3}, annote = {Keywords: abstract visual reasoning, agent-based reasoning, classic algorithm benchmarks, differentiable status registers, explainable graphs, graph generation algorithms, integer sequences, neural combinatorial circuits, recurrent network algorithms, origami folding, Tatham’s puzzles} }
Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)
Andrei Constantinescu, Diana Ghinea, Lioba Heimbach, Zilin Wang, and Roger Wattenhofer. A Fair and Resilient Decentralized Clock Network for Transaction Ordering. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{constantinescu_et_al:LIPIcs.OPODIS.2023.8, author = {Constantinescu, Andrei and Ghinea, Diana and Heimbach, Lioba and Wang, Zilin and Wattenhofer, Roger}, title = {{A Fair and Resilient Decentralized Clock Network for Transaction Ordering}}, booktitle = {27th International Conference on Principles of Distributed Systems (OPODIS 2023)}, pages = {8:1--8:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-308-9}, ISSN = {1868-8969}, year = {2024}, volume = {286}, editor = {Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.8}, URN = {urn:nbn:de:0030-drops-194989}, doi = {10.4230/LIPIcs.OPODIS.2023.8}, annote = {Keywords: Median Validity, Blockchain, Fair Ordering, Front-running Prevention, Miner Extractable Value} }
Published in: LIPIcs, Volume 282, 5th Conference on Advances in Financial Technologies (AFT 2023)
Lioba Heimbach, Eric Schertenleib, and Roger Wattenhofer. DeFi Lending During The Merge. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 9:1-9:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{heimbach_et_al:LIPIcs.AFT.2023.9, author = {Heimbach, Lioba and Schertenleib, Eric and Wattenhofer, Roger}, title = {{DeFi Lending During The Merge}}, booktitle = {5th Conference on Advances in Financial Technologies (AFT 2023)}, pages = {9:1--9:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-303-4}, ISSN = {1868-8969}, year = {2023}, volume = {282}, editor = {Bonneau, Joseph and Weinberg, S. Matthew}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2023.9}, URN = {urn:nbn:de:0030-drops-191985}, doi = {10.4230/LIPIcs.AFT.2023.9}, annote = {Keywords: blockchain, Ethereum, lending protocol, hard fork} }
Published in: Dagstuhl Reports, Volume 12, Issue 11 (2023)
Martin Hoefer, Sigal Oren, Roger Wattenhofer, and Giovanna Varricchio. Computational Social Dynamics (Dagstuhl Seminar 22452). In Dagstuhl Reports, Volume 12, Issue 11, pp. 28-44, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@Article{hoefer_et_al:DagRep.12.11.28, author = {Hoefer, Martin and Oren, Sigal and Wattenhofer, Roger and Varricchio, Giovanna}, title = {{Computational Social Dynamics (Dagstuhl Seminar 22452)}}, pages = {28--44}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2023}, volume = {12}, number = {11}, editor = {Hoefer, Martin and Oren, Sigal and Wattenhofer, Roger and Varricchio, Giovanna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.11.28}, URN = {urn:nbn:de:0030-drops-178346}, doi = {10.4230/DagRep.12.11.28}, annote = {Keywords: algorithmic game theory, behavioral economics, fair division, financial networks, social networks} }
Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)
Roger Wattenhofer. Networks, Dynamics, Algorithms, and Learning (Invited Talk). In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{wattenhofer:LIPIcs.SAND.2022.3, author = {Wattenhofer, Roger}, title = {{Networks, Dynamics, Algorithms, and Learning}}, booktitle = {1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)}, pages = {3:1--3:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-224-2}, ISSN = {1868-8969}, year = {2022}, volume = {221}, editor = {Aspnes, James and Michail, Othon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.3}, URN = {urn:nbn:de:0030-drops-159451}, doi = {10.4230/LIPIcs.SAND.2022.3}, annote = {Keywords: graph neural networks} }
Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)
Adir Morgan, Shay Solomon, and Nicole Wein. Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{morgan_et_al:LIPIcs.DISC.2021.33, author = {Morgan, Adir and Solomon, Shay and Wein, Nicole}, title = {{Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial}}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, pages = {33:1--33:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-210-5}, ISSN = {1868-8969}, year = {2021}, volume = {209}, editor = {Gilbert, Seth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.33}, URN = {urn:nbn:de:0030-drops-148353}, doi = {10.4230/LIPIcs.DISC.2021.33}, annote = {Keywords: Graph Algorithms, Dominating Set, Bounded Arboricity, Linear time algorithms} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Pál András Papp and Roger Wattenhofer. Stabilization Bounds for Influence Propagation from a Random Initial State. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 83:1-83:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{papp_et_al:LIPIcs.MFCS.2021.83, author = {Papp, P\'{a}l Andr\'{a}s and Wattenhofer, Roger}, title = {{Stabilization Bounds for Influence Propagation from a Random Initial State}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {83:1--83:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.83}, URN = {urn:nbn:de:0030-drops-145239}, doi = {10.4230/LIPIcs.MFCS.2021.83}, annote = {Keywords: Majority process, Minority process, Stabilization time, Random initialization, Asynchronous model} }