Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yotam Kenneth and Robert Krauthgamer. Cut Sparsification and Succinct Representation of Submodular Hypergraphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 97:1-97:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kenneth_et_al:LIPIcs.ICALP.2024.97, author = {Kenneth, Yotam and Krauthgamer, Robert}, title = {{Cut Sparsification and Succinct Representation of Submodular Hypergraphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {97:1--97:17}, 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.97}, URN = {urn:nbn:de:0030-drops-202406}, doi = {10.4230/LIPIcs.ICALP.2024.97}, annote = {Keywords: Cut Sparsification, Submodular Hypergraphs, Succinct Representation} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Sanjeev Khanna, Aaron (Louie) Putterman, and Madhu Sudan. Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 98:1-98:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{khanna_et_al:LIPIcs.ICALP.2024.98, author = {Khanna, Sanjeev and Putterman, Aaron (Louie) and Sudan, Madhu}, title = {{Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {98:1--98:17}, 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.98}, URN = {urn:nbn:de:0030-drops-202410}, doi = {10.4230/LIPIcs.ICALP.2024.98}, annote = {Keywords: Sparsification, sketching, hypergraphs} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Farzam Ebrahimnejad, Ansh Nagda, and Shayan Oveis Gharan. Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 61:1-61:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{ebrahimnejad_et_al:LIPIcs.ITCS.2022.61, author = {Ebrahimnejad, Farzam and Nagda, Ansh and Gharan, Shayan Oveis}, title = {{Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {61:1--61:12}, 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.61}, URN = {urn:nbn:de:0030-drops-156579}, doi = {10.4230/LIPIcs.ITCS.2022.61}, annote = {Keywords: perfect matchings, approximate sampling, approximate counting, expanders} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Yu Chen, Sanjeev Khanna, and Ansh Nagda. Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 53:1-53:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{chen_et_al:LIPIcs.ICALP.2021.53, author = {Chen, Yu and Khanna, Sanjeev and Nagda, Ansh}, title = {{Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {53:1--53:21}, 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.53}, URN = {urn:nbn:de:0030-drops-141227}, doi = {10.4230/LIPIcs.ICALP.2021.53}, annote = {Keywords: hypergraphs, graph sparsification, cut queries} }
Feedback for Dagstuhl Publishing