# Smaller Cuts, Higher Lower Bounds

- Published: 31 Oct 2021 Journal: ACM Transactions on Algorithms, volume 17, pages 1-40 (issn: 1549-6325, eissn: 1549-6333, Copyright policy)
- Publisher: Association for Computing Machinery (ACM)

- Link this publication to...
- Cite this publication
Add to ORCID Please grant OpenAIRE to access and update your ORCID works.This research outcome is the result of merged research outcomes in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged research outcome.

doi: 10.1145/3469834

- Weizmann Institute of Science Israel
- Plant Gene Expression Center United States
- Technion – Israel Institute of Technology Israel

- Funder: European Commission (EC)
- Project Code: 755839
- Funding stream: H2020 | ERC | ERC-STG

[1] Amir Abboud, Keren Censor-Hillel, and Seri Khoury. Near-linear lower bounds for distributed distance computations, even in sparse networks. In 30th International Symposium on Distributed Computing, DISC, pages 29{42, 2016.

[2] Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1681{1697, 2015.

[3] Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang. Approximation and xed parameter subquadratic algorithms for radius and diameter in sparse graphs. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 377{391, 2016.

[4] Pierre Aboulker, Marthe Bonamy, Nicolas Bousquet, and Louis Esperet. Distributed coloring in sparse graphs with fewer colors. In ACM Symposium on Principles of Distributed Computing, PODC, pages 419{425, 2018.

[5] Udit Agarwal and Vijaya Ramachandran. A faster deterministic distributed algorithm for weighted apsp through pipelining. CoRR, abs/1804.05441, 2018.

[6] Udit Agarwal, Vijaya Ramachandran, Valerie King, and Matteo Pontecorvi. A deterministic distributed algorithm for exact weighted all-pairs shortest paths in Oe(n3=2) rounds. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC, pages 199{205, 2018.

[7] Kook Jin Ahn and Sudipto Guha. Graph sparsi cation in the semi-streaming model. In Automata, Languages and Programming, 36th Internatilonal Colloquium, ICALP, pages 328{338, 2009.

[8] Matti Astrand, Patrik Floreen, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, and Jara Uitto. A local 2-approximation algorithm for the vertex cover problem. In Proceedings of the 23rd International Symposium on Distributed Computing, DISC, pages 191{205, 2009.

[9] Matti Astrand and Jukka Suomela. Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks. In Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA, pages 294{302, 2010.

[10] Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Gha ari, and Gregory Schwartzman. Distributed approximation of maximum independent set and maximum matching. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC, pages 165{174, 2017.

[11] Reuven Bar-Yehuda, Keren Censor-Hillel, and Gregory Schwartzman. A distributed (2+ )- approximation for vertex cover in o(log / log log ) rounds. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC, pages 3{8, 2016.

[12] Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 623{632, 2002.

[13] Leonid Barenboim. On the locality of some NP-complete problems. In Proceedings of the 39th International Colloquium on Automata, Languages, and Programming, ICALP, pages 403{415, 2012. [OpenAIRE]

[14] Leonid Barenboim. Deterministic ( + 1)-coloring in sublinear (in ) time in static, dynamic, and faulty networks. J. ACM, 63(5):47:1{47:22, 2016.

[15] Leonid Barenboim and Michael Elkin. Deterministic distributed vertex coloring in polylogarithmic time. J. ACM, 58(5):23:1{23:25, 2011.

doi: 10.1145/3469834

- Weizmann Institute of Science Israel
- Plant Gene Expression Center United States
- Technion – Israel Institute of Technology Israel

- Funder: European Commission (EC)
- Project Code: 755839
- Funding stream: H2020 | ERC | ERC-STG

[1] Amir Abboud, Keren Censor-Hillel, and Seri Khoury. Near-linear lower bounds for distributed distance computations, even in sparse networks. In 30th International Symposium on Distributed Computing, DISC, pages 29{42, 2016.

[2] Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1681{1697, 2015.

[3] Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang. Approximation and xed parameter subquadratic algorithms for radius and diameter in sparse graphs. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 377{391, 2016.

[4] Pierre Aboulker, Marthe Bonamy, Nicolas Bousquet, and Louis Esperet. Distributed coloring in sparse graphs with fewer colors. In ACM Symposium on Principles of Distributed Computing, PODC, pages 419{425, 2018.

[5] Udit Agarwal and Vijaya Ramachandran. A faster deterministic distributed algorithm for weighted apsp through pipelining. CoRR, abs/1804.05441, 2018.

[6] Udit Agarwal, Vijaya Ramachandran, Valerie King, and Matteo Pontecorvi. A deterministic distributed algorithm for exact weighted all-pairs shortest paths in Oe(n3=2) rounds. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC, pages 199{205, 2018.

[7] Kook Jin Ahn and Sudipto Guha. Graph sparsi cation in the semi-streaming model. In Automata, Languages and Programming, 36th Internatilonal Colloquium, ICALP, pages 328{338, 2009.

[8] Matti Astrand, Patrik Floreen, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, and Jara Uitto. A local 2-approximation algorithm for the vertex cover problem. In Proceedings of the 23rd International Symposium on Distributed Computing, DISC, pages 191{205, 2009.

[9] Matti Astrand and Jukka Suomela. Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks. In Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA, pages 294{302, 2010.

[10] Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Gha ari, and Gregory Schwartzman. Distributed approximation of maximum independent set and maximum matching. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC, pages 165{174, 2017.

[11] Reuven Bar-Yehuda, Keren Censor-Hillel, and Gregory Schwartzman. A distributed (2+ )- approximation for vertex cover in o(log / log log ) rounds. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC, pages 3{8, 2016.

[12] Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 623{632, 2002.

[13] Leonid Barenboim. On the locality of some NP-complete problems. In Proceedings of the 39th International Colloquium on Automata, Languages, and Programming, ICALP, pages 403{415, 2012. [OpenAIRE]

[14] Leonid Barenboim. Deterministic ( + 1)-coloring in sublinear (in ) time in static, dynamic, and faulty networks. J. ACM, 63(5):47:1{47:22, 2016.

[15] Leonid Barenboim and Michael Elkin. Deterministic distributed vertex coloring in polylogarithmic time. J. ACM, 58(5):23:1{23:25, 2011.