Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Ming Ding and Peng Zhang. Efficient 1-Laplacian Solvers for Well-Shaped Simplicial Complexes: Beyond Betti Numbers and Collapsing Sequences. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 41:1-41:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{ding_et_al:LIPIcs.ESA.2023.41, author = {Ding, Ming and Zhang, Peng}, title = {{Efficient 1-Laplacian Solvers for Well-Shaped Simplicial Complexes: Beyond Betti Numbers and Collapsing Sequences}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {41:1--41:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.41}, URN = {urn:nbn:de:0030-drops-186947}, doi = {10.4230/LIPIcs.ESA.2023.41}, annote = {Keywords: 1-Laplacian Solvers, Simplicial Complexes, Incomplete Nested Dissection} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Rasmus Kyng. An Almost-Linear Time Algorithm for Maximum Flow and More (Invited Talk). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, p. 2:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{kyng:LIPIcs.ICALP.2023.2, author = {Kyng, Rasmus}, title = {{An Almost-Linear Time Algorithm for Maximum Flow and More}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {2:1--2:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.2}, URN = {urn:nbn:de:0030-drops-180543}, doi = {10.4230/LIPIcs.ICALP.2023.2}, annote = {Keywords: Maximum flow, Minimum cost flow, Data structures, Interior point methods, Convex optimization} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Ming Ding, Rasmus Kyng, Maximilian Probst Gutenberg, and Peng Zhang. Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 53:1-53:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{ding_et_al:LIPIcs.ICALP.2022.53, author = {Ding, Ming and Kyng, Rasmus and Gutenberg, Maximilian Probst and Zhang, Peng}, title = {{Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {53:1--53:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.53}, URN = {urn:nbn:de:0030-drops-163945}, doi = {10.4230/LIPIcs.ICALP.2022.53}, annote = {Keywords: Simplicial Complexes, Combinatorial Laplacians, Linear Equations, Fine-Grained Complexity} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Ming Ding, Rasmus Kyng, and Peng Zhang. Two-Commodity Flow Is Equivalent to Linear Programming Under Nearly-Linear Time Reductions. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 54:1-54:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{ding_et_al:LIPIcs.ICALP.2022.54, author = {Ding, Ming and Kyng, Rasmus and Zhang, Peng}, title = {{Two-Commodity Flow Is Equivalent to Linear Programming Under Nearly-Linear Time Reductions}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {54:1--54:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.54}, URN = {urn:nbn:de:0030-drops-163950}, doi = {10.4230/LIPIcs.ICALP.2022.54}, annote = {Keywords: Two-Commodity Flow Problems, Linear Programming, Fine-Grained Complexity} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Sílvia Casacuberta and Rasmus Kyng. Faster Sparse Matrix Inversion and Rank Computation in Finite Fields. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 33:1-33:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{casacuberta_et_al:LIPIcs.ITCS.2022.33, author = {Casacuberta, S{\'\i}lvia and Kyng, Rasmus}, title = {{Faster Sparse Matrix Inversion and Rank Computation in Finite Fields}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {33:1--33:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.33}, URN = {urn:nbn:de:0030-drops-156290}, doi = {10.4230/LIPIcs.ITCS.2022.33}, annote = {Keywords: Matrix inversion, rank computation, displacement operators, numerical linear algebra} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Deeksha Adil, Brian Bullins, Rasmus Kyng, and Sushant Sachdeva. Almost-Linear-Time Weighted 𝓁_p-Norm Solvers in Slightly Dense Graphs via Sparsification. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 9:1-9:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{adil_et_al:LIPIcs.ICALP.2021.9, author = {Adil, Deeksha and Bullins, Brian and Kyng, Rasmus and Sachdeva, Sushant}, title = {{Almost-Linear-Time Weighted 𝓁\underlinep-Norm Solvers in Slightly Dense Graphs via Sparsification}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {9:1--9:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela 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.ICALP.2021.9}, URN = {urn:nbn:de:0030-drops-140782}, doi = {10.4230/LIPIcs.ICALP.2021.9}, annote = {Keywords: Weighted 𝓁\underlinep-norm, Sparsification, Spanners, Iterative Refinement} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Xuangui Huang. Space Hardness of Solving Structured Linear Systems. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 56:1-56:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{huang:LIPIcs.ISAAC.2020.56, author = {Huang, Xuangui}, title = {{Space Hardness of Solving Structured Linear Systems}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {56:1--56:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.56}, URN = {urn:nbn:de:0030-drops-134001}, doi = {10.4230/LIPIcs.ISAAC.2020.56}, annote = {Keywords: linear system solver, logarithmic space, threshold circuit} }
Feedback for Dagstuhl Publishing