Cited By
View all- Assadi S(2023)Recent Advances in Multi-Pass Graph Streaming Lower BoundsACM SIGACT News10.1145/3623800.362380854:3(48-75)Online publication date: 11-Sep-2023
Smaller Cuts, Higher Lower Bounds
Article No.: 30, Pages 1 - 40
Abstract
This article proves strong lower bounds for distributed computing in the congest model, by presenting the bit-gadget: a new technique for constructing graphs with small cuts.
The contribution of bit-gadgets is twofold. First, developing careful sparse graph constructions with small cuts extends known techniques to show a near-linear lower bound for computing the diameter, a result previously known only for dense graphs. Moreover, the sparseness of the construction plays a crucial role in applying it to approximations of various distance computation problems, drastically improving over what can be obtained when using dense graphs.
Second, small cuts are essential for proving super-linear lower bounds, none of which were known prior to this work. In fact, they allow us to show near-quadratic lower bounds for several problems, such as exact minimum vertex cover or maximum independent set, as well as for coloring a graph with its chromatic number. Such strong lower bounds are not limited to NP-hard problems, as given by two simple graph problems in P, which are shown to require a quadratic and near-quadratic number of rounds. All of the above are optimal up to logarithmic factors. In addition, in this context, the complexity of the all-pairs-shortest-paths problem is discussed.
Finally, it is shown that graph constructions for congest lower bounds translate to lower bounds for the semi-streaming model, despite being very different in its nature.
References
[1]
Amir Abboud, Keren Censor-Hillel, and Seri Khoury. 2016. Near-linear lower bounds for distributed distance computations, even in sparse networks. In Proceedings of the 30th International Symposium on Distributed Computing (DISC’16). 29–42.
[2]
Amir Abboud, Vincent Cohen-Addad, and Philip N. Klein. 2020. New hardness results for planar graph problems in p and an algorithm for sparsest cut. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC’20). 996–1009.
[3]
Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. 2015. Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA’15). 1681–1697.
[4]
Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang. 2016. Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA’16). 377–391.
[5]
Pierre Aboulker, Marthe Bonamy, Nicolas Bousquet, and Louis Esperet. 2018. Distributed Coloring in Sparse Graphs with Fewer Colors. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC’18). 419–425.
[6]
Udit Agarwal and Vijaya Ramachandran. 2018. A Faster Deterministic Distributed Algorithm for Weighted APSP Through Pipelining. Retrieved from https://arxiv.org/abs/1807.08824.
[7]
Udit Agarwal, Vijaya Ramachandran, Valerie King, and Matteo Pontecorvi. 2018. A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in Rounds. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC’18). 199–205.
[8]
Kook Jin Ahn and Sudipto Guha. 2009. Graph Sparsification in the Semi-streaming Model. In Proceedings of the 36th Internatilonal Colloquium on Automata, Languages and Programming (ICALP’09). 328–338.
[9]
Matti Åstrand, Patrik Floréen, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, and Jara Uitto. 2009. A Local 2-Approximation Algorithm for the Vertex Cover Problem. In Proceedings of the 23rd International Symposium on Distributed Computing (DISC’09). 191–205.
[10]
Matti Åstrand and Jukka Suomela. 2010. 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’10). 294–302.
[11]
Nir Bachrach, Keren Censor-Hillel, Michal Dory, Yuval Efron, Dean Leitersdorf, and Ami Paz. 2019. Hardness of Distributed Optimization. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC’19). ACM, 238–247.
[12]
Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Ghaffari, and Gregory Schwartzman. 2017. Distributed Approximation of Maximum Independent Set and Maximum Matching. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC’17). 165–174.
[13]
Reuven Bar-Yehuda, Keren Censor-Hillel, and Gregory Schwartzman. 2016. A Distributed (2+)-Approximation for Vertex Cover in O(log/ log log ) Rounds. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC’16). 3–8.
[14]
Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. 2002. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’02). 623–632.
[15]
Leonid Barenboim. 2012. On the Locality of Some NP-Complete Problems. In Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP’12). 403–415.
[16]
Leonid Barenboim. 2016. Deterministic ( + 1)-Coloring in Sublinear (in ) Time in Static, Dynamic, and Faulty Networks. J. ACM 63, 5 (2016), 47:1–47:22.
[17]
Leonid Barenboim and Michael Elkin. 2011. Deterministic Distributed Vertex Coloring in Polylogarithmic Time. J. ACM 58, 5 (2011), 23:1–23:25.
[18]
Leonid Barenboim and Michael Elkin. 2014. Combinatorial algorithms for distributed graph coloring. Distrib. Comput. 27, 2 (2014), 79–93.
[19]
Leonid Barenboim, Michael Elkin, and Fabian Kuhn. 2014. Distributed (Delta+1)-Coloring in Linear (in Delta) Time. SIAM J. Comput. 43, 1 (2014), 72–95.
[20]
Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. 2016. The Locality of Distributed Symmetry Breaking. J. ACM 63, 3 (2016), 20:1–20:45.
[21]
Surender Baswana. 2008. Streaming algorithm for graph spanners—Single pass and constant processing time per edge. Info. Process. Lett. 106, 3 (2008), 110–114.
[22]
Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. 2017. Near-optimal approximate shortest paths and transshipment in distributed and streaming models. In Proceedings of the 31st International Symposium on Distributed Computing (DISC’17) (LIPIcs), Andréa W. Richa (Ed.), Vol. 91. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 7:1–7:16.
[23]
Suman Kalyan Bera and Prantar Ghosh. 2018. Retrieved from https://arxiv.org/abs/1807.07640.
[24]
Aaron Bernstein and Danupon Nanongkai. 2019. Distributed exact weighted all-pairs shortest paths in near-linear time. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC’19). 334–342.
[25]
Marijke H. L. Bodlaender, Magnús M. Halldórsson, Christian Konrad, and Fabian Kuhn. 2016. Brief Announcement: Local Independent Set Approximation. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC’16). 93–95.
[26]
Ilaria Bordino, Debora Donato, Aristides Gionis, and Stefano Leonardi. 2008. Mining Large Networks with Subgraph Counting. In Proceedings of the 8th IEEE International Conference on Data Mining (ICDM’08). 737–742.
[27]
Vladimir Braverman, Zaoxing Liu, Tejasvam Singh, N. V. Vinodchandran, and Lin F. Yang. 2018. New bounds for the CLIQUE-GAP problem using graph decomposition theory. Algorithmica 80, 2 (2018), 652–667.
[28]
Karl Bringmann and Sebastian Krinninger. 2018. A note on hardness of diameter approximation. Info. Process. Lett. 133 (2018), 10–15.
[29]
Luciana S. Buriol, Gereon Frahling, Stefano Leonardi, and Christian Sohler. 2007. Estimating Clustering Indexes in Data Streams. In Proceedings of the 15th Annual European Symposium on Algorithms (ESA’07). 618–632.
[30]
Massimo Cairo, Roberto Grossi, and Romeo Rizzi. 2016. New bounds for approximating extremal distances in undirected graphs. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’16). 363–376.
[31]
Keren Censor-Hillel, Telikepalli Kavitha, Ami Paz, and Amir Yehudayoff. 2018. Distributed construction of purely additive spanners. Distrib. Comput. 31, 3 (2018), 223–240.
[32]
Keren Censor-Hillel, Seri Khoury, and Ami Paz. 2017. Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model. In Proceedings of the 31st International Symposium on Distributed Computing (DISC’17). 10:1–10:16.
[33]
Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. 2016. An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model. In Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS’16). 615–624.
[34]
Yi-Jun Chang and Seth Pettie. 2017. A Time Hierarchy Theorem for the LOCAL Model. Retrieved from https://arxiv.org/abs/1704.06297.
[35]
Shiri Chechik, Daniel H. Larkin, Liam Roditty, Grant Schoenebeck, Robert Endre Tarjan, and Virginia Vassilevska Williams. 2014. Better Approximation Algorithms for the Graph Diameter. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA’14). 1041–1052.
[36]
Shiri Chechik and Doron Mukhtar. 2018. Optimal Distributed Coloring Algorithms for Planar Graphs in the LOCAL model. Retrieved from https://arxiv.org/abs/1804.00137.
[37]
Rajesh Hemant Chitnis, Graham Cormode, Mohammad Taghi Hajiaghayi, and Morteza Monemizadeh. 2015. Parameterized Streaming: Maximal Matching and Vertex Cover. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’15). 1234–1251.
[38]
Kai-Min Chung, Seth Pettie, and Hsin-Hao Su. 2014. Distributed algorithms for the Lovász local lemma and graph coloring. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC’14). 134–143.
[39]
Richard Cole and Uzi Vishkin. 1986. Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking. Info. Control 70, 1 (1986), 32–53.
[40]
Graham Cormode, Jacques Dark, and Christian Konrad. 2018. Approximating the Caro-Wei Bound for Independent Sets in Graph Streams. In Proceedings of the 5th International Symposium on Combinatorial Optimization (ISCO’18). 101–114.
[41]
Andrzej Czygrinow, Michal Hanckowiak, and Wojciech Wawrzyniak. 2008. Fast Distributed Approximations in Planar Graphs. In Proceedings of the 22nd International Symposium on Distributed Computing (DISC’08). 78–92.
[42]
Irit Dinur and Igor Shinkar. 2010. On the conditional hardness of coloring a 4-colorable graph with super-constant number of colors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, 138–151.
[43]
Andrew Drucker, Fabian Kuhn, and Rotem Oshman. 2014. On the power of the congested clique model. In Proceedings of the 33rd ACM Symposium on Principles of Distributed Computing (PODC’14). 367–376.
[44]
Michael Elkin. 2006. An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem. SIAM J. Comput. 36, 2 (2006), 433–456.
[45]
Michael Elkin. 2011. Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. ACM Trans. Algor. 7, 2 (2011), 20:1–20:17.
[46]
Michael Elkin. 2017. Distributed exact shortest paths in sublinear time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC’17). 757–770.
[47]
Michael Elkin and Jian Zhang. 2004. Efficient algorithms for constructing -spanners in the distributed and streaming models. In Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC’04). 160–168.
[48]
Yuval Emek, Christoph Pfister, Jochen Seidel, and Roger Wattenhofer. 2014. Anonymous networks: randomization = 2-hop coloring. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC’14). 96–105.
[49]
Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. 2005. On graph problems in a semi-streaming model. Theor. Comput. Sci. 348, 2–3 (2005), 207–216.
[50]
Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. 2008. Graph Distances in the Data-Stream Model. SIAM J. Comput. 38, 5 (2008), 1709–1727.
[51]
Pierre Fraigniaud, Cyril Gavoille, David Ilcinkas, and Andrzej Pelc. 2009. Distributed computing with advice: information sensitivity of graph coloring. Distrib. Comput. 21, 6 (2009), 395–403.
[52]
Pierre Fraigniaud, Marc Heinrich, and Adrian Kosowski. 2016. Local Conflict Coloring. In Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS’16). 625–634.
[53]
Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer. 2012. Networks cannot compute their diameter in sublinear time. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA’12). 1150–1162.
[54]
Fabrizio Grandoni, Jochen Könemann, and Alessandro Panconesi. 2008. Distributed weighted vertex cover via maximal matchings. ACM Trans. Algor. 5, 1 (2008), 6:1–6:12.
[55]
Fabrizio Grandoni, Jochen Könemann, Alessandro Panconesi, and Mauro Sozio. 2008. A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover. SIAM J. Comput. 38, 3 (2008), 825–840.
[56]
Ofer Grossman, Seri Khoury, and Ami Paz. 2020. Improved Hardness of Approximation of Diameter in the CONGEST Model. In Proceedings of the 34th International Symposium on Distributed Computing (DISC’20) (LIPIcs), Vol. 179. 19:1–19:16.
[57]
Venkatesan Guruswami and Sanjeev Khanna. 2004. On the Hardness of 4-Coloring a 3-Colorable Graph. SIAM J. Discret. Math. 18, 1 (2004), 30–40.
[58]
Bjarni V. Halldórsson, Magnús M. Halldórsson, Elena Losievskaja, and Mario Szegedy. 2016. Streaming Algorithms for Independent Sets in Sparse Hypergraphs. Algorithmica 76, 2 (2016), 490–501.
[59]
Magnús M. Halldórsson, Xiaoming Sun, Mario Szegedy, and Chengu Wang. 2012. Streaming and Communication Complexity of Clique Approximation. In Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP’12). 449–460.
[60]
Michal Hanckowiak, Michal Karonski, and Alessandro Panconesi. 2001. On the Distributed Complexity of Computing Maximal Matchings. SIAM J. Discrete Math. 15, 1 (2001), 41–57.
[61]
David G. Harris, Johannes Schneider, and Hsin-Hao Su. 2016. Distributed (+1)-coloring in sublogarithmic rounds. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC’16). 465–478.
[62]
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. 2016. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC’16). 489–498.
[63]
Monika Rauch Henzinger, Prabhakar Raghavan, and Sridhar Rajagopalan. 1998. Computing on data streams. In External Memory Algorithms. Springer, 107–118.
[64]
Stephan Holzer, David Peleg, Liam Roditty, and Roger Wattenhofer. 2014. Distributed 3/2-Approximation of the Diameter. In Proceedings of the 28th International Symposium on Distributed Computing (DISC’14). 562–564.
[65]
Stephan Holzer and Nathan Pinsker. 2015. Approximation of Distances and Shortest Paths in the Broadcast Congest Clique. In Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS’15). 6:1–6:16.
[66]
Stephan Holzer and Roger Wattenhofer. 2012. Optimal distributed all pairs shortest paths and applications. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC’12). 355–364.
[67]
Qiang-Sheng Hua, Haoqiang Fan, Lixiang Qian, Ming Ai, Yangyang Li, Xuanhua Shi, and Hai Jin. 2016. Brief Announcement: A Tight Distributed Algorithm for All Pairs Shortest Paths and Applications. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA’16). 439–441.
[68]
Chien-Chung Huang, Danupon Nanongkai, and Thatchaphol Saranurak. 2017. Distributed Exact Weighted All-Pairs Shortest Paths in Rounds. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS’17). 168–179.
[69]
Michael Kapralov. 2013. Better bounds for matchings in the streaming model. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA’13). 1679–1697.
[70]
Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. 2015. Streaming Lower Bounds for Approximating MAX-CUT. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA’15). 1263–1282.
[71]
Jonathan A. Kelner and Alex Levin. 2013. Spectral Sparsification in the Semi-streaming Setting. Theory Comput. Syst. 53, 2 (2013), 243–262.
[72]
Samir Khuller, Uzi Vishkin, and Neal E. Young. 1994. A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Covers. J. Algor. 17, 2 (1994), 280–289.
[73]
Christos Koufogiannakis and Neal E. Young. 2009. Distributed and parallel algorithms for weighted vertex cover and other covering problems. In Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing (PODC’09). 171–179.
[74]
Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. 2006. The price of being near-sighted. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’06). 980–989.
[75]
Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. 2016. Local Computation: Lower and Upper Bounds. J. ACM 63, 2 (2016), 17:1–17:44.
[76]
Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press, New York, NY.
[77]
Christoph Lenzen. 2019. Theory of Distributed Systems, Lecture 8: Distance Approximation and Routing. Retrieved from https://www.mpi-inf.mpg.de/fileadmin/inf/d1/teaching/winter19/tods/ToDS_08.pdf.
[78]
Christoph Lenzen and Boaz Patt-Shamir. 2015. Fast Partial Distance Estimation and Applications. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC’15). 153–162.
[79]
Christoph Lenzen and David Peleg. 2013. Efficient distributed source detection with limited bandwidth. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC’13). 375–382.
[80]
Christoph Lenzen and Roger Wattenhofer. 2008. Leveraging Linial’s Locality Limit. In Proceedings of the 22nd International Symposium on Distributed Computing (DISC’08). 394–407.
[81]
Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http://snap.stanford.edu/data.
[82]
Jason Li and Merav Parter. 2019. Planar diameter via metric compression. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC’19). 152–163.
[83]
Nathan Linial. 1992. Locality in Distributed Graph Algorithms. SIAM J. Comput. 21, 1 (1992), 193–201.
[84]
Madhusudan Manjunath, Kurt Mehlhorn, Konstantinos Panagiotou, and He Sun. 2011. Approximate Counting of Cycles in Streams. In Proceedings of the 19th Annual European Symposium on Algorithms (ESA’11). 677–688.
[85]
Robert Meusel, Sebastiano Vigna, Oliver Lehmberg, and Christian Bizer. 2015. The Graph Structure in the Web—Analyzed on Different Aggregation Levels. J. Web Sci. 1, 1 (2015), 33–47.
[86]
Thomas Moscibroda and Roger Wattenhofer. 2008. Coloring unstructured radio networks. Distrib. Comput. 21, 4 (2008), 271–284.
[87]
S. Muthukrishnan. 2005. Data Streams: Algorithms and Applications. Found. Trends Theor. Comput. Sci. 1, 2 (2005).
[88]
Danupon Nanongkai. 2014. Distributed approximation algorithms for weighted shortest paths. In Proceedings of the Symposium on Theory of Computing (STOC’14). 565–573.
[89]
Danupon Nanongkai, Atish Das Sarma, and Gopal Pandurangan. 2011. A tight unconditional lower bound on distributed randomwalk computation. In Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing (PODC’11). 257–266.
[90]
Alessandro Panconesi and Romeo Rizzi. 2001. Some simple distributed algorithms for sparse networks. Distrib. Comput. 14, 2 (2001), 97–100.
[91]
Ami Paz and Gregory Schwartzman. 2017. A -Approximation for Maximum Weight Matching in the Semi-Streaming Model. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA’17). 2153–2161.
[92]
David Peleg. 2000. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA.
[93]
David Peleg, Liam Roditty, and Elad Tal. 2012. Distributed Algorithms for Network Diameter and Girth. In Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP’12). 660–672.
[94]
David Peleg and Vitaly Rubinovich. 2000. A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction. SIAM J. Comput. 30, 5 (2000), 1427–1442.
[95]
Seth Pettie and Hsin-Hao Su. 2015. Distributed coloring algorithms for triangle-free graphs. Info. Comput. 243 (2015), 263–280.
[96]
Valentin Polishchuk and Jukka Suomela. 2009. A simple local 3-approximation algorithm for vertex cover. Info. Process. Lett. 109, 12 (2009), 642–645.
[97]
Alexander A. Razborov. 1992. On the Distributional Complexity of Disjointness. Theor. Comput. Sci. 106, 2 (1992), 385–390.
[98]
Liam Roditty and Virginia Vassilevska Williams. 2013. Fast approximation algorithms for the diameter and radius of sparse graphs. In Proceedings of the Symposium on Theory of Computing Conference (STOC’13). 515–524.
[99]
Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. 2012. Distributed Verification and Hardness of Distributed Approximation. SIAM J. Comput. 41, 5 (2012), 1235–1265.
[100]
Johannes Schneider, Michael Elkin, and Roger Wattenhofer. 2013. Symmetry breaking depending on the chromatic number or the neighborhood growth. Theor. Comput. Sci. 509 (2013), 40–50.
[101]
Andrew Chi-Chih Yao. 1979. Some Complexity Questions Related to Distributive Computing (Preliminary Report). In Proceedings of the 11h Annual ACM Symposium on Theory of Computing (STOC’79). 209–213.
Index Terms
- Smaller Cuts, Higher Lower Bounds
Recommendations
Distributed Lower Bounds for Ruling Sets
Given a graph $G=(V,E)$, an $(\alpha,\beta)$-ruling set is a subset $S\subseteq V$ such that the distance between any two vertices in $S$ is at least $\alpha$, and the distance between any vertex in $V$ and the closest vertex in $S$ is at most $\beta$. We ...
Higher Lower Bounds for Near-Neighbor and Further Rich Problems
We convert cell-probe lower bounds for polynomial space into stronger lower bounds for near-linear space. Our technique applies to any lower bound proved through the richness method. For example, it applies to partial match and to near-neighbor problems,...
A Tight Lower Bound for 3-Coloring Grids in the Online-LOCAL Model
PODC '24: Proceedings of the 43rd ACM Symposium on Principles of Distributed ComputingRecently, Akbari et al. (ICALP 2023) studied the locality of graph problems in distributed, sequential, dynamic, and online settings from a unified point of view. They designed a novel O(log n)-locality deterministic algorithm for proper 3-coloring ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2021
280 pages
Copyright © 2021 Association for Computing Machinery.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 04 October 2021
Accepted: 01 June 2021
Revised: 01 February 2021
Received: 01 November 2019
Published in TALG Volume 17, Issue 4
Check for updates
Author Tags
Qualifiers
- Research-article
- Refereed
Funding Sources
- European Union’s Horizon 2020 research and innovation programme
- Israel Science Foundation
- Austrian Science Fund (FWF) and netIDEE SCIENCE
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 121Total Downloads
- Downloads (Last 12 months)33
- Downloads (Last 6 weeks)3
Reflects downloads up to 30 Sep 2024
Other Metrics
Citations
Cited By
View all- Assadi S(2023)Recent Advances in Multi-Pass Graph Streaming Lower BoundsACM SIGACT News10.1145/3623800.362380854:3(48-75)Online publication date: 11-Sep-2023
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format