Document Open Access Logo

On the Probe Complexity of Local Computation Algorithms

Authors Uriel Feige, Boaz Patt-Shamir, Shai Vardi

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.50.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

Uriel Feige
  • Weizmann Institute of Science, Rehovot, Israel
Boaz Patt-Shamir
  • Tel Aviv University, Tel Aviv, Israel
Shai Vardi
  • California Institute of Technology, Pasadena, CA, USA

Funding

  • Feige, Uriel: Supported in part by the Israel Science Foundation (grant No. 1388/16). Work partly done in Microsoft Research, Herzeliya, Israel.
  • Patt-Shamir, Boaz: Supported in part by the Israel Science Foundation (grant No. 1444/14).
  • Vardi, Shai: Supported in part by the I-CORE in Algorithms Postdoctoral Fellowship, the Linde Foundation and NSF grants CNS-1254169 and CNS-1518941. Part of the research was carried out when Shai was a postdoctoral researcher at the Weizmann Institute of Science.

Cite As Get BibTex

Uriel Feige, Boaz Patt-Shamir, and Shai Vardi. On the Probe Complexity of Local Computation Algorithms. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 50:1-50:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.50

Abstract

In the Local Computation Algorithms (LCA) model, the algorithm is asked to compute a part of the output by reading as little as possible from the input. For example, an LCA for coloring a graph is given a vertex name (as a "query"), and it should output the color assigned to that vertex after inquiring about some part of the graph topology using "probes"; all outputs must be consistent with the same coloring. LCAs are useful when the input is huge, and the output as a whole is not needed simultaneously. Most previous work on LCAs was limited to bounded-degree graphs, which seems inevitable because probes are of the form "what vertex is at the other end of edge i of vertex v?". In this work we study LCAs for unbounded-degree graphs. In particular, such LCAs are expected to probe the graph a number of times that is significantly smaller than the maximum, average, or even minimum degree. We show that there are problems that have very efficient LCAs on any graph - specifically, we show that there is an LCA for the weak coloring problem (where a coloring is legal if every vertex has a neighbor with a different color) that uses log^* n+O(1) probes to reply to any query. As another way of dealing with large degrees, we propose a more powerful type of probe which we call a strong probe: given a vertex name, it returns a list of its neighbors. Lower bounds for strong probes are stronger than ones in the edge probe model (which we call weak probes). Our main result in this model is that roughly Omega(sqrt{n}) strong probes are required to compute a maximal matching.
Our findings include interesting separations between closely related problems. For weak probes, we show that while weak 3-coloring can be done with probe complexity log^* n+O(1), weak 2-coloring has probe complexity Omega(log n/log log n). For strong probes, our negative result for maximal matching is complemented by an LCA for (1-epsilon)-approximate maximum matching on regular graphs that uses O(1) strong probes, for any constant epsilon>0.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • Local computation algorithms
  • sublinear algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Noga Alon, Ronitt Rubinfeld, Shai Vardi, and Ning Xie. Space-efficient local computation algorithms. In Proc. 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1132-1139, 2012. Google Scholar
  2. Reid Andersen. A local algorithm for finding dense subgraphs. ACM Trans. Algorithms, 6(4), 2010. Google Scholar
  3. Reid Andersen, Shayan Oveis Gharan, Yuval Peres, and Luca Trevisan. Almost optimal local graph clustering using evolving sets. J. ACM, 63(2):15, 2016. Google Scholar
  4. Vincent D Blondel, Julien M Hendrickx, Alex Olshevsky, and John N Tsitsiklis. Convergence in multiagent coordination, consensus, and flocking. In Proceedings of IEEE Conference on Decision and Control, pages 2996-3000. IEEE, 2005. Google Scholar
  5. Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan. Approximating the minimum spanning tree weight in sublinear time. SIAM J. Comput., 34(6):1370-1379, 2005. Google Scholar
  6. Guy Even, Moti Medina, and Dana Ron. Best of two local models: Local centralized and local distributed algorithms. CoRR, abs/1402.3796, 2014. URL: http://arxiv.org/abs/1402.3796,
  7. Guy Even, Moti Medina, and Dana Ron. Distributed maximum matching in bounded degree graphs. In Proceedings of the 2015 International Conference on Distributed Computing and Networking, ICDCN, pages 18:1-18:10, 2015. Google Scholar
  8. Uriel Feige, Yishay Mansour, and Robert E. Schapire. Learning and inference in the presence of corrupted inputs. In Proceedings of The 28th Conference on Learning Theory, COLT, pages 637-657, 2015. Google Scholar
  9. Uriel Feige, Boaz Patt-Shamir, and Shai Vardi. On the probe complexity of local computation algorithms. CoRR, abs/1703.07734, 2017. URL: http://arxiv.org/abs/1703.07734.
  10. Pierre Fraigniaud, Marc Heinrich, and Adrian Kosowski. Local conflict coloring. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS, pages 625-634, 2016. Google Scholar
  11. David Gamarnik and David A. Goldberg. Randomized greedy algorithms for independent sets and matchings in regular graphs: Exact results and finite girth corrections. Combinatorics, Probability and Computing, 19:61-85, 1 2010. URL: http://dx.doi.org/10.1017/S0963548309990186.
  12. Mohsen Ghaffari. An improved distributed algorithm for maximal independent set. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pages 270-277, 2016. Google Scholar
  13. Andrew V. Goldberg, Serge A. Plotkin, and Gregory E. Shannon. Parallel symmetry-breaking in sparse graphs. SIAM J. Discret. Math., 1(4):434-446, 1988. Google Scholar
  14. Oded Goldreich and Dana Ron. Property testing in bounded degree graphs. Algorithmica, 32(2):302-343, 2002. Google Scholar
  15. Mika Göös, Juho Hirvonen, Reut Levi, Moti Medina, and Jukka Suomela. Non-local probes do not help with many graph problems. Distributed Computing - 30th International Symposium, DISC, pages 201-214, 2016. Google Scholar
  16. Avinatan Hassidim, Yishay Mansour, and Shai Vardi. Local computation mechanism design. ACM Trans. Economics and Comput., 4(4):21:1-21:24, 2016. URL: http://dx.doi.org/10.1145/2956584.
  17. M. Jha and S. Raskhodnikova. Testing and reconstruction of Lipschitz functions with applications to data privacy. In Proc. 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2011. Google Scholar
  18. J. Katz and L. Trevisan. On the efficiency of local decoding procedures for error-correcting codes. In Proc. 32nd Annual ACM Symposium on the Theory of Computing (STOC), pages 80-86, 2000. Google Scholar
  19. Reut Levi, Dana Ron, and Ronitt Rubinfeld. Local algorithms for sparse spanning graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 826-842, 2014. Google Scholar
  20. Reut Levi, Ronitt Rubinfeld, and Anak Yodpinyanee. Brief announcement: Local computation algorithms for graphs of non-constant degrees. In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA, pages 59-61, 2015. Google Scholar
  21. Nathan Linial. Locality in distributed graph algorithms. SIAM J. Comput., 21(1), 1992. Google Scholar
  22. Palma London, Niangjun Chen, Shai Vardi, and Adam Wierman. Distributed optimization via local computation algorithms. http://users.cms.caltech.edu/~plondon/loco.pdf, 2017.
  23. Steven H Low, Fernando Paganini, and John C Doyle. Internet congestion control. IEEE control systems, 22(1):28-43, 2002. Google Scholar
  24. Michael Luby. A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput., 15(4):1036-1053, 1986. Google Scholar
  25. Nancy A. Lynch. Upper bounds for static resource allocation in a distributed system. J. Comput. Syst. Sci., 23(2):254-278, 1981. Google Scholar
  26. Yishay Mansour, Boaz Patt-Shamir, and Shai Vardi. Constant-time local computation algorithms. Theory of Computing Systems, pages 1-19, 2017. Google Scholar
  27. Yishay Mansour, Aviad Rubinstein, Shai Vardi, and Ning Xie. Converting online algorithms to local computation algorithms. In Proc. 39th International Colloquium on Automata, Languages and Programming (ICALP), pages 653-664, 2012. Google Scholar
  28. Moni Naor. A lower bound on probabilistic algorithms for distributive ring coloring. SIAM J. Discrete Math., 4(3):409-412, 1991. Google Scholar
  29. Moni Naor and Larry J. Stockmeyer. What can be computed locally? SIAM J. Comput., 24(6):1259-1277, 1995. Google Scholar
  30. Huy N. Nguyen and Krzystof Onak. Constant-time approximation algorithms via local improvements. In Proc. 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 327-336, 2008. Google Scholar
  31. M. Parnas and D. Ron. Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theoretical Computer Science, 381(1-3), 2007. Google Scholar
  32. Omer Reingold and Shai Vardi. New techniques and tighter bounds for local computation algorithms. J. Comput. Syst. Sci., 82(7):1180-1200, 2016. Google Scholar
  33. Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. Fast local computation algorithms. In Proc. 2nd Symposium on Innovations in Computer Science (ICS), pages 223-238, 2011. Google Scholar
  34. Michael E. Saks and C. Seshadhri. Local monotonicity reconstruction. SIAM J. Comput., 39(7):2897-2926, 2010. Google Scholar
  35. Daniel A. Spielman and Shang-Hua Teng. A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM J. Comput., 42(1):1-26, 2013. Google Scholar
  36. Shai Vardi. Designing Local Computation Algorithms and Mechanisms. PhD thesis, Tel Aviv University, Tel Aviv, Israel, 2015. Google Scholar
  37. Vijay V. Vazirani. Approximation Algorithms. Springer, 2001. Google Scholar
  38. Andrew Chi-Chin Yao. Probabilistic computations: Toward a unified measure of complexity. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science, FOCS '77, pages 222-227, 1977. Google Scholar
  39. Sergey Yekhanin. Locally decodable codes. Foundations and Trends in Theoretical Computer Science, 6(3):139-255, 2012. Google Scholar
  40. Yuichi Yoshida, Masaki Yamamoto, and Hiro Ito. Improved constant-time approximation algorithms for maximum matchings and other optimization problems. SIAM J. Comput., 41(4):1074-1093, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact