Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Konrad Anand, Weiming Feng, Graham Freifeld, Heng Guo, and Jiaheng Wang. Approximate Counting for Spin Systems in Sub-Quadratic Time. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{anand_et_al:LIPIcs.ICALP.2024.11, author = {Anand, Konrad and Feng, Weiming and Freifeld, Graham and Guo, Heng and Wang, Jiaheng}, title = {{Approximate Counting for Spin Systems in Sub-Quadratic Time}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {11:1--11: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.11}, URN = {urn:nbn:de:0030-drops-201543}, doi = {10.4230/LIPIcs.ICALP.2024.11}, annote = {Keywords: Randomised algorithm, Approximate counting, Spin system, Sub-quadratic algorithm} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Amartya Shankha Biswas, Ronitt Rubinfeld, and Anak Yodpinyanee. Local Access to Huge Random Objects Through Partial Sampling. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 27:1-27:65, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{biswas_et_al:LIPIcs.ITCS.2020.27, author = {Biswas, Amartya Shankha and Rubinfeld, Ronitt and Yodpinyanee, Anak}, title = {{Local Access to Huge Random Objects Through Partial Sampling}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {27:1--27:65}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.27}, URN = {urn:nbn:de:0030-drops-117126}, doi = {10.4230/LIPIcs.ITCS.2020.27}, annote = {Keywords: sublinear time algorithms, random generation, local computation} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Merav Parter, Ronitt Rubinfeld, Ali Vakilian, and Anak Yodpinyanee. Local Computation Algorithms for Spanners. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 58:1-58:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{parter_et_al:LIPIcs.ITCS.2019.58, author = {Parter, Merav and Rubinfeld, Ronitt and Vakilian, Ali and Yodpinyanee, Anak}, title = {{Local Computation Algorithms for Spanners}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {58:1--58:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.58}, URN = {urn:nbn:de:0030-drops-101510}, doi = {10.4230/LIPIcs.ITCS.2019.58}, annote = {Keywords: Local Computation Algorithms, Sub-linear Algorithms, Graph Spanners} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Jonathan Ullman, Ali Vakilian, and Anak Yodpinyanee. Fractional Set Cover in the Streaming Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{indyk_et_al:LIPIcs.APPROX-RANDOM.2017.12, author = {Indyk, Piotr and Mahabadi, Sepideh and Rubinfeld, Ronitt and Ullman, Jonathan and Vakilian, Ali and Yodpinyanee, Anak}, title = {{Fractional Set Cover in the Streaming Model}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {12:1--12:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-044-6}, ISSN = {1868-8969}, year = {2017}, volume = {81}, editor = {Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.12}, URN = {urn:nbn:de:0030-drops-75613}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.12}, annote = {Keywords: Streaming Algorithms, Fractional Set Cover, LP relaxation, Multiplicative Weight Update} }