Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Manuel Cáceres, Brendan Mumey, Santeri Toivonen, and Alexandru I. Tomescu. Practical Minimum Path Cover. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{caceres_et_al:LIPIcs.SEA.2024.3, author = {C\'{a}ceres, Manuel and Mumey, Brendan and Toivonen, Santeri and Tomescu, Alexandru I.}, title = {{Practical Minimum Path Cover}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {3:1--3:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.3}, URN = {urn:nbn:de:0030-drops-203687}, doi = {10.4230/LIPIcs.SEA.2024.3}, annote = {Keywords: minimum path cover, directed acyclic graph, maximum flow, parameterized algorithms, edge sparsification, algorithm engineering} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Giovanna Kobus Conrado, Amir Kafshdar Goharshady, Pavel Hudec, Pingjiang Li, and Harshit Jitendra Motwani. Faster Treewidth-Based Approximations for Wiener Index. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{conrado_et_al:LIPIcs.SEA.2024.6, author = {Conrado, Giovanna Kobus and Goharshady, Amir Kafshdar and Hudec, Pavel and Li, Pingjiang and Motwani, Harshit Jitendra}, title = {{Faster Treewidth-Based Approximations for Wiener Index}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {6:1--6:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.6}, URN = {urn:nbn:de:0030-drops-203718}, doi = {10.4230/LIPIcs.SEA.2024.6}, annote = {Keywords: Computational Chemistry, Treewidth, Wiener Index} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Li Chen and Mingquan Ye. High-Accuracy Multicommodity Flows via Iterative Refinement. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chen_et_al:LIPIcs.ICALP.2024.45, author = {Chen, Li and Ye, Mingquan}, title = {{High-Accuracy Multicommodity Flows via Iterative Refinement}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {45:1--45: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.45}, URN = {urn:nbn:de:0030-drops-201887}, doi = {10.4230/LIPIcs.ICALP.2024.45}, annote = {Keywords: High-accuracy multicommodity flow, Iterative refinement framework, Convex flow solver} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Bruno Loff and Mateusz Skomra. Smoothed Analysis of Deterministic Discounted and Mean-Payoff Games. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 147:1-147:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{loff_et_al:LIPIcs.ICALP.2024.147, author = {Loff, Bruno and Skomra, Mateusz}, title = {{Smoothed Analysis of Deterministic Discounted and Mean-Payoff Games}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {147:1--147:16}, 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.147}, URN = {urn:nbn:de:0030-drops-202908}, doi = {10.4230/LIPIcs.ICALP.2024.147}, annote = {Keywords: Mean-payoff games, discounted games, policy iteration, smoothed analysis} }
Published in: TGDK, Volume 2, Issue 1 (2024): Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge, Volume 2, Issue 1
Pieter Bonte, Jean-Paul Calbimonte, Daniel de Leng, Daniele Dell'Aglio, Emanuele Della Valle, Thomas Eiter, Federico Giannini, Fredrik Heintz, Konstantin Schekotihin, Danh Le-Phuoc, Alessandra Mileo, Patrik Schneider, Riccardo Tommasini, Jacopo Urbani, and Giacomo Ziffer. Grounding Stream Reasoning Research. In Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge (TGDK), Volume 2, Issue 1, pp. 2:1-2:47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@Article{bonte_et_al:TGDK.2.1.2, author = {Bonte, Pieter and Calbimonte, Jean-Paul and de Leng, Daniel and Dell'Aglio, Daniele and Della Valle, Emanuele and Eiter, Thomas and Giannini, Federico and Heintz, Fredrik and Schekotihin, Konstantin and Le-Phuoc, Danh and Mileo, Alessandra and Schneider, Patrik and Tommasini, Riccardo and Urbani, Jacopo and Ziffer, Giacomo}, title = {{Grounding Stream Reasoning Research}}, journal = {Transactions on Graph Data and Knowledge}, pages = {2:1--2:47}, ISSN = {2942-7517}, year = {2024}, volume = {2}, number = {1}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/TGDK.2.1.2}, URN = {urn:nbn:de:0030-drops-198597}, doi = {10.4230/TGDK.2.1.2}, annote = {Keywords: Stream Reasoning, Stream Processing, RDF streams, Streaming Linked Data, Continuous query processing, Temporal Logics, High-performance computing, Databases} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Paul W. Goldberg and Alexandros Hollender. The Hairy Ball Problem is PPAD-Complete. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 65:1-65:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{goldberg_et_al:LIPIcs.ICALP.2019.65, author = {Goldberg, Paul W. and Hollender, Alexandros}, title = {{The Hairy Ball Problem is PPAD-Complete}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {65:1--65:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.65}, URN = {urn:nbn:de:0030-drops-106416}, doi = {10.4230/LIPIcs.ICALP.2019.65}, annote = {Keywords: Computational Complexity, TFNP, PPAD, End-of-Line} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Paul W. Goldberg, and Jie Zhang. Hardness Results for Consensus-Halving. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{filosratsikas_et_al:LIPIcs.MFCS.2018.24, author = {Filos-Ratsikas, Aris and Frederiksen, S{\o}ren Kristoffer Stiil and Goldberg, Paul W. and Zhang, Jie}, title = {{Hardness Results for Consensus-Halving}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {24:1--24:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.24}, URN = {urn:nbn:de:0030-drops-96069}, doi = {10.4230/LIPIcs.MFCS.2018.24}, annote = {Keywords: PPAD, PPA, consensus halving, generalized-circuit, reduction} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Paul W. Goldberg and Christos H. Papadimitriou. Towards a Unified Complexity Theory of Total Functions. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{goldberg_et_al:LIPIcs.ITCS.2018.37, author = {Goldberg, Paul W. and Papadimitriou, Christos H.}, title = {{Towards a Unified Complexity Theory of Total Functions}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {37:1--37:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-060-6}, ISSN = {1868-8969}, year = {2018}, volume = {94}, editor = {Karlin, Anna R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.37}, URN = {urn:nbn:de:0030-drops-83403}, doi = {10.4230/LIPIcs.ITCS.2018.37}, annote = {Keywords: Computational complexity, first-order logic, proof system, NP search functions, TFNP} }
Published in: Dagstuhl Reports, Volume 7, Issue 6 (2018)
Paul W. Goldberg, Yishay Mansour, and Paul Dütting. Game Theory Meets Computational Learning Theory (Dagstuhl Seminar 17251). In Dagstuhl Reports, Volume 7, Issue 6, pp. 68-85, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@Article{goldberg_et_al:DagRep.7.6.68, author = {Goldberg, Paul W. and Mansour, Yishay and D\"{u}tting, Paul}, title = {{Game Theory Meets Computational Learning Theory (Dagstuhl Seminar 17251)}}, pages = {68--85}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2017}, volume = {7}, number = {6}, editor = {Goldberg, Paul W. and Mansour, Yishay and D\"{u}tting, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.6.68}, URN = {urn:nbn:de:0030-drops-82876}, doi = {10.4230/DagRep.7.6.68}, annote = {Keywords: Algorithmic Game Theory, Computational Learning Theory, Economics} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Paul W. Goldberg. Algorithmic Game Theory (Tutorial). In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, p. 20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{goldberg:LIPIcs.STACS.2015.20, author = {Goldberg, Paul W.}, title = {{Algorithmic Game Theory}}, booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)}, pages = {20--20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-78-1}, ISSN = {1868-8969}, year = {2015}, volume = {30}, editor = {Mayr, Ernst W. and Ollinger, Nicolas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.20}, URN = {urn:nbn:de:0030-drops-49606}, doi = {10.4230/LIPIcs.STACS.2015.20}, annote = {Keywords: equilibrium, non-cooperative games, computational complexity} }