{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T04:15:37Z","timestamp":1747455337226,"version":"3.40.5"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662460771"},{"type":"electronic","value":"9783662460788"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-46078-8_31","type":"book-chapter","created":{"date-parts":[[2015,1,14]],"date-time":"2015-01-14T14:54:29Z","timestamp":1421247269000},"page":"377-388","source":"Crossref","is-referenced-by-count":2,"title":["Filling Logarithmic Gaps in Distributed Complexity for Global Problems"],"prefix":"10.1007","author":[{"given":"Hiroaki","family":"Ookawa","sequence":"first","affiliation":[]},{"given":"Taisuke","family":"Izumi","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"31_CR1","doi-asserted-by":"crossref","unstructured":"Sarma, A.D., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. In: Proc. of the 43rd Annual ACM Symposium on Theory of Computing, pp. 363\u2013372 (2011)","DOI":"10.1145\/1993636.1993686"},{"key":"31_CR2","doi-asserted-by":"crossref","unstructured":"Dinitz, Y., Moran, S., Rajsbaum, S.: Bit complexity of breaking and achieving symmetry in chains and rings. Journal of the ACM\u00a055(1) (2008)","DOI":"10.1145\/1326554.1326557"},{"key":"31_CR3","doi-asserted-by":"crossref","unstructured":"Elkin, M.: An unconditional lower bound on the hardness of approximation of distributed minimum spanning tree problem. In: Proc the 30th ACM Symposium on Theory of Computing(STOC), pp. 331\u2013340 (2004)","DOI":"10.1145\/1007352.1007407"},{"issue":"1","key":"31_CR4","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1137\/S0097539794261118","volume":"27","author":"J.A. Garay","year":"1998","unstructured":"Garay, J.A., Kutten, S., Peleg, D.: A sublinear time distributed algorithm for minimum-weight spanning trees. SIAM Journal on Computing\u00a027(1), 302\u2013316 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"31_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-41527-2_1","volume-title":"Distributed Computing","author":"M. Ghaffari","year":"2013","unstructured":"Ghaffari, M., Kuhn, F.: Distributed minimum cut approximation. In: Afek, Y. (ed.) DISC 2013. LNCS, vol.\u00a08205, pp. 1\u201315. Springer, Heidelberg (2013)"},{"key":"31_CR6","doi-asserted-by":"crossref","unstructured":"Holzer, S., Wattenhofer, R.: Optimal distributed all pairs shortest paths and applications. In: Proc. of the 2012 ACM Symposium on Principles of Distributed Computing (PODC), pp. 355\u2013364 (2012)","DOI":"10.1145\/2332432.2332504"},{"key":"31_CR7","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press (1997)","DOI":"10.1017\/CBO9780511574948"},{"key":"31_CR8","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Patt-Shamir, B.: Fast routing table construction using small messages: Extended abstract. In: Proc. of the 45th Annual ACM Symposium on Symposium on Theory of Computing (STOC), pp. 381\u2013390 (2013)","DOI":"10.1145\/2488608.2488656"},{"key":"31_CR9","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Peleg, D.: Efficient distributed source detection with limited bandwidth. In: Proc. of the 2013 ACM Symposium on Principles of Distributed Computing (PODC), pp. 375\u2013382 (2013)","DOI":"10.1145\/2484239.2484262"},{"issue":"6","key":"31_CR10","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/s00446-005-0127-6","volume":"18","author":"Z. Lotker","year":"2006","unstructured":"Lotker, Z., Patt-Shamir, B., Peleg, D.: Distributed mst for constant diameter graphs. Distributed Computing\u00a018(6), 453\u2013460 (2006)","journal-title":"Distributed Computing"},{"key":"31_CR11","doi-asserted-by":"crossref","unstructured":"Nanongkai, D.: Distributed approximation algorithms for weighted shortest paths. In: Proc. of the 46th ACM Symposium on Theory of Computing (STOC), pp. 565\u2013573 (2014)","DOI":"10.1145\/2591796.2591850"},{"key":"31_CR12","doi-asserted-by":"crossref","unstructured":"Nanongkai, D., Das Sarma, A., Pandurangan, G.: A tight unconditional lower bound on distributed random walk computation. In: Proc. of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pp. 257\u2013266 (2011)","DOI":"10.1145\/1993806.1993853"},{"key":"31_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"660","DOI":"10.1007\/978-3-642-31585-5_58","volume-title":"Automata, Languages, and Programming","author":"D. Peleg","year":"2012","unstructured":"Peleg, D., Roditty, L., Tal, E.: Distributed algorithms for network diameter and girth. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part II. LNCS, vol.\u00a07392, pp. 660\u2013672. Springer, Heidelberg (2012)"},{"issue":"5","key":"31_CR14","doi-asserted-by":"publisher","first-page":"1427","DOI":"10.1137\/S0097539700369740","volume":"30","author":"D. Peleg","year":"2000","unstructured":"Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM Journal on Computing\u00a030(5), 1427\u20131442 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"31_CR15","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Some complexity questions related to distributive computing(preliminary report). In: Proc. of the 11th Annual ACM Symposium on Theory of Computing (STOC), pp. 209\u2013213 (1979)","DOI":"10.1145\/800135.804414"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2015: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-46078-8_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,16]],"date-time":"2025-05-16T22:16:57Z","timestamp":1747433817000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-46078-8_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662460771","9783662460788"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-46078-8_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}