[{"publication":"35th Conference on Neural Information Processing Systems","article_processing_charge":"No","language":[{"iso":"eng"}],"year":"2021","acknowledgement":"We gratefully acknowledge funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). PD partly conducted this work while at IST Austria and was supported by the European Union’s Horizon 2020 programme under the Marie Skłodowska-Curie grant agreement No. 754411. SL was funded in part by European Research Council (ERC) under the European Union’s Horizon 2020 programme (grant agreement DAPP, No. 678880, and EPiGRAM-HS, No. 801039).\r\n","title":"Asynchronous decentralized SGD with quantized and local updates","main_file_link":[{"url":"https://papers.nips.cc/paper/2021/hash/362c99307cdc3f2d8b410652386a9dd1-Abstract.html","open_access":"1"}],"ec_funded":1,"related_material":{"record":[{"id":"10429","relation":"dissertation_contains","status":"public"}]},"conference":{"end_date":"2021-12-14","start_date":"2021-12-06","name":"NeurIPS: Neural Information Processing Systems","location":"Sydney, Australia"},"oa_version":"Published Version","citation":{"apa":"Nadiradze, G., Sabour, A., Davies, P., Li, S., &#38; Alistarh, D.-A. (2021). Asynchronous decentralized SGD with quantized and local updates. In <i>35th Conference on Neural Information Processing Systems</i>. Sydney, Australia: Neural Information Processing Systems Foundation.","short":"G. Nadiradze, A. Sabour, P. Davies, S. Li, D.-A. Alistarh, in:, 35th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2021.","ista":"Nadiradze G, Sabour A, Davies P, Li S, Alistarh D-A. 2021. Asynchronous decentralized SGD with quantized and local updates. 35th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems.","chicago":"Nadiradze, Giorgi, Amirmojtaba Sabour, Peter Davies, Shigang Li, and Dan-Adrian Alistarh. “Asynchronous Decentralized SGD with Quantized and Local Updates.” In <i>35th Conference on Neural Information Processing Systems</i>. Neural Information Processing Systems Foundation, 2021.","ama":"Nadiradze G, Sabour A, Davies P, Li S, Alistarh D-A. Asynchronous decentralized SGD with quantized and local updates. In: <i>35th Conference on Neural Information Processing Systems</i>. Neural Information Processing Systems Foundation; 2021.","ieee":"G. Nadiradze, A. Sabour, P. Davies, S. Li, and D.-A. Alistarh, “Asynchronous decentralized SGD with quantized and local updates,” in <i>35th Conference on Neural Information Processing Systems</i>, Sydney, Australia, 2021.","mla":"Nadiradze, Giorgi, et al. “Asynchronous Decentralized SGD with Quantized and Local Updates.” <i>35th Conference on Neural Information Processing Systems</i>, Neural Information Processing Systems Foundation, 2021."},"date_updated":"2023-10-17T11:48:56Z","type":"conference","date_published":"2021-12-01T00:00:00Z","month":"12","publisher":"Neural Information Processing Systems Foundation","status":"public","date_created":"2021-12-09T10:59:12Z","department":[{"_id":"DaAl"}],"day":"01","arxiv":1,"oa":1,"quality_controlled":"1","external_id":{"arxiv":["1910.12308"]},"author":[{"full_name":"Nadiradze, Giorgi","last_name":"Nadiradze","orcid":"0000-0001-5634-0731","first_name":"Giorgi","id":"3279A00C-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Sabour, Amirmojtaba","id":"bcc145fd-e77f-11ea-ae8b-80d661dbff67","first_name":"Amirmojtaba","last_name":"Sabour"},{"full_name":"Davies, Peter","id":"11396234-BB50-11E9-B24C-90FCE5697425","last_name":"Davies","orcid":"0000-0002-5646-9524","first_name":"Peter"},{"last_name":"Li","first_name":"Shigang","full_name":"Li, Shigang"},{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian"}],"project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","call_identifier":"H2020"},{"grant_number":"805223","call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425","name":"Elastic Coordination for Scalable Machine Learning"}],"_id":"10435","abstract":[{"text":"Decentralized optimization is emerging as a viable alternative for scalable distributed machine learning, but also introduces new challenges in terms of synchronization costs. To this end, several communication-reduction techniques, such as non-blocking communication, quantization, and local steps, have been explored in the decentralized setting. Due to the complexity of analyzing optimization in such a relaxed setting, this line of work often assumes \\emph{global} communication rounds, which require additional synchronization. In this paper, we consider decentralized optimization in the simpler, but harder to analyze, \\emph{asynchronous gossip} model, in which communication occurs in discrete, randomly chosen pairings among nodes. Perhaps surprisingly, we show that a variant of SGD called \\emph{SwarmSGD} still converges in this setting, even if \\emph{non-blocking communication}, \\emph{quantization}, and \\emph{local steps} are all applied \\emph{in conjunction}, and even if the node data distributions and underlying graph topology are both \\emph{heterogenous}. Our analysis is based on a new connection with multi-dimensional load-balancing processes. We implement this algorithm and deploy it in a super-computing environment, showing that it can outperform previous decentralized methods in terms of end-to-end training time, and that it can even rival carefully-tuned large-batch SGD for certain tasks.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published"},{"abstract":[{"lang":"eng","text":"We study efficient distributed algorithms for the fundamental problem of principal component analysis and leading eigenvector computation on the sphere, when the data are randomly distributed among a set of computational nodes. We propose a new quantized variant of Riemannian gradient descent to solve this problem, and prove that the algorithm converges with high probability under a set of necessary spherical-convexity properties. We give bounds on the number of bits transmitted by the algorithm under common initialization schemes, and investigate the dependency on the problem dimension in each case."}],"_id":"11452","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","external_id":{"arxiv":["2110.14391"]},"author":[{"first_name":"Foivos","last_name":"Alimisis","full_name":"Alimisis, Foivos"},{"full_name":"Davies, Peter","first_name":"Peter","last_name":"Davies","orcid":"0000-0002-5646-9524","id":"11396234-BB50-11E9-B24C-90FCE5697425"},{"last_name":"Vandereycken","first_name":"Bart","full_name":"Vandereycken, Bart"},{"orcid":"0000-0003-3650-940X","last_name":"Alistarh","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian"}],"project":[{"call_identifier":"H2020","grant_number":"805223","_id":"268A44D6-B435-11E9-9278-68D0E5697425","name":"Elastic Coordination for Scalable Machine Learning"},{"name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"754411"}],"volume":4,"publication_identifier":{"isbn":["9781713845393"],"issn":["1049-5258"]},"day":"01","department":[{"_id":"DaAl"}],"quality_controlled":"1","arxiv":1,"oa":1,"page":"2823-2834","publisher":"Neural Information Processing Systems Foundation","status":"public","date_created":"2022-06-19T22:01:58Z","citation":{"chicago":"Alimisis, Foivos, Peter Davies, Bart Vandereycken, and Dan-Adrian Alistarh. “Distributed Principal Component Analysis with Limited Communication.” In <i>Advances in Neural Information Processing Systems - 35th Conference on Neural Information Processing Systems</i>, 4:2823–34. Neural Information Processing Systems Foundation, 2021.","ista":"Alimisis F, Davies P, Vandereycken B, Alistarh D-A. 2021. Distributed principal component analysis with limited communication. Advances in Neural Information Processing Systems - 35th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems vol. 4, 2823–2834.","short":"F. Alimisis, P. Davies, B. Vandereycken, D.-A. Alistarh, in:, Advances in Neural Information Processing Systems - 35th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2021, pp. 2823–2834.","apa":"Alimisis, F., Davies, P., Vandereycken, B., &#38; Alistarh, D.-A. (2021). Distributed principal component analysis with limited communication. In <i>Advances in Neural Information Processing Systems - 35th Conference on Neural Information Processing Systems</i> (Vol. 4, pp. 2823–2834). Virtual, Online: Neural Information Processing Systems Foundation.","mla":"Alimisis, Foivos, et al. “Distributed Principal Component Analysis with Limited Communication.” <i>Advances in Neural Information Processing Systems - 35th Conference on Neural Information Processing Systems</i>, vol. 4, Neural Information Processing Systems Foundation, 2021, pp. 2823–34.","ieee":"F. Alimisis, P. Davies, B. Vandereycken, and D.-A. Alistarh, “Distributed principal component analysis with limited communication,” in <i>Advances in Neural Information Processing Systems - 35th Conference on Neural Information Processing Systems</i>, Virtual, Online, 2021, vol. 4, pp. 2823–2834.","ama":"Alimisis F, Davies P, Vandereycken B, Alistarh D-A. Distributed principal component analysis with limited communication. In: <i>Advances in Neural Information Processing Systems - 35th Conference on Neural Information Processing Systems</i>. Vol 4. Neural Information Processing Systems Foundation; 2021:2823-2834."},"date_updated":"2022-06-20T08:31:52Z","type":"conference","date_published":"2021-12-01T00:00:00Z","month":"12","scopus_import":"1","conference":{"name":"NeurIPS: Neural Information Processing Systems","start_date":"2021-12-06","end_date":"2021-12-14","location":"Virtual, Online"},"ec_funded":1,"oa_version":"Published Version","acknowledgement":"We would like to thank the anonymous reviewers for helpful comments and suggestions. We also thank Aurelien Lucchi and Antonio Orvieto for fruitful discussions at an early stage of this work. FA is partially supported by the SNSF under research project No. 192363 and conducted part of this work while at IST Austria under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 805223 ScaleML). PD partly conducted this work while at IST Austria and was supported by the European Union’s Horizon 2020 programme under the Marie Skłodowska-Curie grant agreement No. 754411.","intvolume":"         4","title":"Distributed principal component analysis with limited communication","main_file_link":[{"open_access":"1","url":"https://proceedings.neurips.cc/paper/2021/file/1680e9fa7b4dd5d62ece800239bb53bd-Paper.pdf"}],"publication":"Advances in Neural Information Processing Systems - 35th Conference on Neural Information Processing Systems","article_processing_charge":"No","year":"2021","language":[{"iso":"eng"}]},{"external_id":{"arxiv":["2102.07214"]},"author":[{"last_name":"Alimisis","first_name":"Foivos","full_name":"Alimisis, Foivos"},{"full_name":"Davies, Peter","id":"11396234-BB50-11E9-B24C-90FCE5697425","first_name":"Peter","orcid":"0000-0002-5646-9524","last_name":"Davies"},{"full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh"}],"project":[{"_id":"268A44D6-B435-11E9-9278-68D0E5697425","name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223","call_identifier":"H2020"},{"grant_number":"754411","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"publication_identifier":{"eissn":["2640-3498"],"isbn":["9781713845065"]},"volume":139,"abstract":[{"text":"We investigate fast and communication-efficient algorithms for the classic problem of minimizing a sum of strongly convex and smooth functions that are distributed among n\r\n different nodes, which can communicate using a limited number of bits. Most previous communication-efficient approaches for this problem are limited to first-order optimization, and therefore have \\emph{linear} dependence on the condition number in their communication complexity. We show that this dependence is not inherent: communication-efficient methods can in fact have sublinear dependence on the condition number. For this, we design and analyze the first communication-efficient distributed variants of preconditioned gradient descent for Generalized Linear Models, and for Newton’s method. Our results rely on a new technique for quantizing both the preconditioner and the descent direction at each step of the algorithms, while controlling their convergence rate. We also validate our findings experimentally, showing faster convergence and reduced communication relative to previous methods.","lang":"eng"}],"_id":"13147","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"file_name":"2021_PMLR_Alimisis.pdf","access_level":"open_access","checksum":"7ec0d59bac268b49c76bf2e036dedd7a","date_created":"2023-06-19T10:41:05Z","success":1,"creator":"dernst","date_updated":"2023-06-19T10:41:05Z","file_size":429087,"content_type":"application/pdf","relation":"main_file","file_id":"13154"}],"page":"196-206","publisher":"ML Research Press","date_created":"2023-06-18T22:00:48Z","status":"public","day":"01","department":[{"_id":"DaAl"}],"quality_controlled":"1","oa":1,"arxiv":1,"conference":{"name":"International Conference on Machine Learning","start_date":"2021-07-18","end_date":"2021-07-24","location":"Virtual"},"ec_funded":1,"oa_version":"Published Version","file_date_updated":"2023-06-19T10:41:05Z","type":"conference","citation":{"short":"F. Alimisis, P. Davies, D.-A. Alistarh, in:, Proceedings of the 38th International Conference on Machine Learning, ML Research Press, 2021, pp. 196–206.","apa":"Alimisis, F., Davies, P., &#38; Alistarh, D.-A. (2021). Communication-efficient distributed optimization with quantized preconditioners. In <i>Proceedings of the 38th International Conference on Machine Learning</i> (Vol. 139, pp. 196–206). Virtual: ML Research Press.","chicago":"Alimisis, Foivos, Peter Davies, and Dan-Adrian Alistarh. “Communication-Efficient Distributed Optimization with Quantized Preconditioners.” In <i>Proceedings of the 38th International Conference on Machine Learning</i>, 139:196–206. ML Research Press, 2021.","ista":"Alimisis F, Davies P, Alistarh D-A. 2021. Communication-efficient distributed optimization with quantized preconditioners. Proceedings of the 38th International Conference on Machine Learning. International Conference on Machine Learning vol. 139, 196–206.","ama":"Alimisis F, Davies P, Alistarh D-A. Communication-efficient distributed optimization with quantized preconditioners. In: <i>Proceedings of the 38th International Conference on Machine Learning</i>. Vol 139. ML Research Press; 2021:196-206.","mla":"Alimisis, Foivos, et al. “Communication-Efficient Distributed Optimization with Quantized Preconditioners.” <i>Proceedings of the 38th International Conference on Machine Learning</i>, vol. 139, ML Research Press, 2021, pp. 196–206.","ieee":"F. Alimisis, P. Davies, and D.-A. Alistarh, “Communication-efficient distributed optimization with quantized preconditioners,” in <i>Proceedings of the 38th International Conference on Machine Learning</i>, Virtual, 2021, vol. 139, pp. 196–206."},"date_updated":"2023-06-19T10:44:38Z","has_accepted_license":"1","license":"https://creativecommons.org/licenses/by/4.0/","ddc":["000"],"date_published":"2021-07-01T00:00:00Z","month":"07","scopus_import":"1","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"article_processing_charge":"No","publication":"Proceedings of the 38th International Conference on Machine Learning","language":[{"iso":"eng"}],"year":"2021","acknowledgement":"The authors would like to thank Janne Korhonen, Aurelien Lucchi, Celestine MendlerDunner and Antonio Orvieto for helpful discussions. FA ¨and DA were supported during this work by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). PD was supported by the European Union’s Horizon 2020 programme under the Marie Skłodowska-Curie grant agreement No. 754411.","title":"Communication-efficient distributed optimization with quantized preconditioners","intvolume":"       139"},{"intvolume":"        17","title":"Graph sparsification for derandomizing massively parallel computation with low space","main_file_link":[{"url":"https://arxiv.org/abs/1912.05390","open_access":"1"}],"acknowledgement":"Institute of Science and Technology Austria (IST Austria). Email: peter.davies@ist.ac.at. Work partially\r\ndone at the Department of Computer Science and Centre for Discrete Mathematics and its Applications (DIMAP),University of Warwick. Research partially supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 754411, the Centre for Discrete Mathematics and its Applications, a Weizmann-UK Making Connections Grant, and EPSRC award EP/N011163/1.","year":"2021","language":[{"iso":"eng"}],"article_processing_charge":"No","publication":"ACM Transactions on Algorithms","month":"06","date_published":"2021-06-01T00:00:00Z","ddc":["000"],"article_number":"16","date_updated":"2024-02-28T12:53:09Z","citation":{"ama":"Czumaj A, Davies P, Parter M. Graph sparsification for derandomizing massively parallel computation with low space. <i>ACM Transactions on Algorithms</i>. 2021;17(2). doi:<a href=\"https://doi.org/10.1145/3451992\">10.1145/3451992</a>","ieee":"A. Czumaj, P. Davies, and M. Parter, “Graph sparsification for derandomizing massively parallel computation with low space,” <i>ACM Transactions on Algorithms</i>, vol. 17, no. 2. Association for Computing Machinery, 2021.","mla":"Czumaj, Artur, et al. “Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space.” <i>ACM Transactions on Algorithms</i>, vol. 17, no. 2, 16, Association for Computing Machinery, 2021, doi:<a href=\"https://doi.org/10.1145/3451992\">10.1145/3451992</a>.","apa":"Czumaj, A., Davies, P., &#38; Parter, M. (2021). Graph sparsification for derandomizing massively parallel computation with low space. <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3451992\">https://doi.org/10.1145/3451992</a>","short":"A. Czumaj, P. Davies, M. Parter, ACM Transactions on Algorithms 17 (2021).","ista":"Czumaj A, Davies P, Parter M. 2021. Graph sparsification for derandomizing massively parallel computation with low space. ACM Transactions on Algorithms. 17(2), 16.","chicago":"Czumaj, Artur, Peter Davies, and Merav Parter. “Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space.” <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3451992\">https://doi.org/10.1145/3451992</a>."},"has_accepted_license":"1","type":"journal_article","file_date_updated":"2021-06-10T19:33:56Z","oa_version":"Submitted Version","ec_funded":1,"related_material":{"record":[{"status":"public","id":"7802","relation":"earlier_version"}]},"article_type":"original","doi":"10.1145/3451992","arxiv":1,"issue":"2","oa":1,"quality_controlled":"1","department":[{"_id":"DaAl"}],"isi":1,"day":"01","status":"public","date_created":"2021-06-10T19:31:05Z","publisher":"Association for Computing Machinery","file":[{"checksum":"a21c627683890c309a68f6389302c408","date_created":"2021-06-10T19:33:56Z","success":1,"file_name":"MISMM-arxiv.pdf","access_level":"open_access","relation":"main_file","file_id":"9542","date_updated":"2021-06-10T19:33:56Z","creator":"pdavies","file_size":587404,"content_type":"application/pdf"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","_id":"9541","abstract":[{"text":"The Massively Parallel Computation (MPC) model is an emerging model that distills core aspects of distributed and parallel computation, developed as a tool to solve combinatorial (typically graph) problems in systems of many machines with limited space. Recent work has focused on the regime in which machines have sublinear (in n, the number of nodes in the input graph) space, with randomized algorithms presented for the fundamental problems of Maximal Matching and Maximal Independent Set. However, there have been no prior corresponding deterministic algorithms. A major challenge underlying the sublinear space setting is that the local space of each machine might be too small to store all edges incident to a single node. This poses a considerable obstacle compared to classical models in which each node is assumed to know and have easy access to its incident edges. To overcome this barrier, we introduce a new graph sparsification technique that deterministically computes a low-degree subgraph, with the additional property that solving the problem on this subgraph provides significant progress towards solving the problem for the original input graph. Using this framework to derandomize the well-known algorithm of Luby [SICOMP’86], we obtain O(log Δ + log log n)-round deterministic MPC algorithms for solving the problems of Maximal Matching and Maximal Independent Set with O(nɛ) space on each machine for any constant ɛ > 0. These algorithms also run in O(log Δ) rounds in the closely related model of CONGESTED CLIQUE, improving upon the state-of-the-art bound of O(log 2Δ) rounds by Censor-Hillel et al. [DISC’17].","lang":"eng"}],"volume":17,"publication_identifier":{"eissn":["1549-6333"],"issn":["1549-6325"]},"project":[{"call_identifier":"H2020","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"external_id":{"arxiv":["1912.05390"],"isi":["000661311300006"]},"author":[{"first_name":"Artur","last_name":"Czumaj","full_name":"Czumaj, Artur"},{"full_name":"Davies, Peter","first_name":"Peter","orcid":"0000-0002-5646-9524","last_name":"Davies","id":"11396234-BB50-11E9-B24C-90FCE5697425"},{"first_name":"Merav","last_name":"Parter","full_name":"Parter, Merav"}]},{"day":"01","department":[{"_id":"DaAl"}],"title":"New bounds for distributed mean estimation and variance reduction","main_file_link":[{"open_access":"1","url":"https://openreview.net/pdf?id=t86MwoUCCNe"}],"quality_controlled":"1","oa":1,"arxiv":1,"publication":"9th International Conference on Learning Representations","article_processing_charge":"No","date_created":"2021-06-10T19:46:08Z","status":"public","language":[{"iso":"eng"}],"year":"2021","type":"conference","abstract":[{"lang":"eng","text":"We consider the problem ofdistributed mean estimation (DME), in which n machines are each given a local d-dimensional vector xv∈Rd, and must cooperate to estimate the mean of their inputs μ=1n∑nv=1xv, while minimizing total communication cost. DME is a fundamental construct in distributed machine learning, and there has been considerable work on variants of this problem, especially in the context of distributed variance reduction for stochastic gradients in parallel SGD. Previous work typically assumes an upper bound on the norm of the input vectors, and achieves an error bound in terms of this norm. However, in many real applications, the input vectors are concentrated around the correct output μ, but μ itself has large norm. In such cases, previous output error bounds perform poorly. In this paper, we show that output error bounds need not depend on input norm. We provide a method of quantization which allows distributed mean estimation to be performed with solution quality dependent only on the distance between inputs, not on input norm, and show an analogous result for distributed variance reduction. The technique is based on a new connection with lattice theory. We also provide lower bounds showing that the communication to error trade-off of our algorithms is asymptotically optimal. As the lattices achieving optimal bounds under l2-norm can be computationally impractical, we also present an extension which leverages easy-to-use cubic lattices, and is loose only up to a logarithmic factor ind. We show experimentally that our method yields practical improvements for common applications, relative to prior approaches."}],"date_updated":"2023-02-23T14:00:40Z","citation":{"ama":"Davies P, Gurunanthan V, Moshrefi N, Ashkboos S, Alistarh D-A. New bounds for distributed mean estimation and variance reduction. In: <i>9th International Conference on Learning Representations</i>. ; 2021.","ieee":"P. Davies, V. Gurunanthan, N. Moshrefi, S. Ashkboos, and D.-A. Alistarh, “New bounds for distributed mean estimation and variance reduction,” in <i>9th International Conference on Learning Representations</i>, Virtual, 2021.","mla":"Davies, Peter, et al. “New Bounds for Distributed Mean Estimation and Variance Reduction.” <i>9th International Conference on Learning Representations</i>, 2021.","apa":"Davies, P., Gurunanthan, V., Moshrefi, N., Ashkboos, S., &#38; Alistarh, D.-A. (2021). New bounds for distributed mean estimation and variance reduction. In <i>9th International Conference on Learning Representations</i>. Virtual.","short":"P. Davies, V. Gurunanthan, N. Moshrefi, S. Ashkboos, D.-A. Alistarh, in:, 9th International Conference on Learning Representations, 2021.","ista":"Davies P, Gurunanthan V, Moshrefi N, Ashkboos S, Alistarh D-A. 2021. New bounds for distributed mean estimation and variance reduction. 9th International Conference on Learning Representations.  ICLR: International Conference on Learning Representations.","chicago":"Davies, Peter, Vijaykrishna Gurunanthan, Niusha  Moshrefi, Saleh Ashkboos, and Dan-Adrian Alistarh. “New Bounds for Distributed Mean Estimation and Variance Reduction.” In <i>9th International Conference on Learning Representations</i>, 2021."},"_id":"9543","publication_status":"published","month":"05","date_published":"2021-05-01T00:00:00Z","user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","conference":{"end_date":"2021-05-07","start_date":"2021-05-03","name":" ICLR: International Conference on Learning Representations","location":"Virtual"},"external_id":{"arxiv":["2002.09268"]},"author":[{"first_name":"Peter","last_name":"Davies","orcid":"0000-0002-5646-9524","id":"11396234-BB50-11E9-B24C-90FCE5697425","full_name":"Davies, Peter"},{"first_name":"Vijaykrishna","last_name":"Gurunanthan","full_name":"Gurunanthan, Vijaykrishna"},{"id":"4db776ff-ce15-11eb-96e3-bc2b90b01c16","first_name":"Niusha ","last_name":"Moshrefi","full_name":"Moshrefi, Niusha "},{"id":"0D0A9058-257B-11EA-A937-9341C3D8BC8A","last_name":"Ashkboos","first_name":"Saleh","full_name":"Ashkboos, Saleh"},{"full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"}],"ec_funded":1,"project":[{"grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships"}],"oa_version":"Published Version"},{"file":[{"file_name":"Population_Coupon_Collector.pdf","access_level":"open_access","checksum":"fe37fb9af3f5016c1084af9d6e7109bd","date_created":"2021-07-01T11:21:40Z","creator":"pdavies","date_updated":"2021-07-01T11:21:40Z","file_size":319728,"content_type":"application/pdf","relation":"main_file","file_id":"9621"}],"publisher":"Springer Nature","page":"3-12","date_created":"2021-07-01T11:04:43Z","status":"public","department":[{"_id":"DaAl"}],"day":"20","oa":1,"quality_controlled":"1","author":[{"full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X"},{"orcid":"0000-0002-5646-9524","last_name":"Davies","first_name":"Peter","id":"11396234-BB50-11E9-B24C-90FCE5697425","full_name":"Davies, Peter"}],"publication_identifier":{"issn":["0302-9743"],"eisbn":["9783030795276"],"eissn":["1611-3349"],"isbn":["9783030795269"]},"volume":12810,"project":[{"grant_number":"754411","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"_id":"9620","abstract":[{"text":"In this note, we introduce a distributed twist on the classic coupon collector problem: a set of m collectors wish to each obtain a set of n coupons; for this, they can each sample coupons uniformly at random, but can also meet in pairwise interactions, during which they can exchange coupons. By doing so, they hope to reduce the number of coupons that must be sampled by each collector in order to obtain a full set. This extension is natural when considering real-world manifestations of the coupon collector phenomenon, and has been remarked upon and studied empirically (Hayes and Hannigan 2006, Ahmad et al. 2014, Delmarcelle 2019).\r\n\r\nWe provide the first theoretical analysis for such a scenario. We find that “coupon collecting with friends” can indeed significantly reduce the number of coupons each collector must sample, and raises interesting connections to the more traditional variants of the problem. While our analysis is in most cases asymptotically tight, there are several open questions raised, regarding finer-grained analysis of both “coupon collecting with friends,” and of a long-studied variant of the original problem in which a collector requires multiple full sets of coupons.","lang":"eng"}],"publication_status":"published","user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","article_processing_charge":"No","publication":"Structural Information and Communication Complexity","year":"2021","language":[{"iso":"eng"}],"acknowledgement":"Peter Davies is supported by the European Union’s Horizon2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 754411.","title":"Collecting coupons is faster with friends","intvolume":"     12810","ec_funded":1,"doi":"10.1007/978-3-030-79527-6_1","conference":{"location":"Wrocław, Poland","end_date":"2021-07-01","name":" SIROCCO: International Colloquium on Structural Information and Communication Complexity","start_date":"2021-06-28"},"alternative_title":["LNCS"],"file_date_updated":"2021-07-01T11:21:40Z","oa_version":"Preprint","type":"conference","has_accepted_license":"1","date_updated":"2023-02-23T14:02:46Z","citation":{"ama":"Alistarh D-A, Davies P. Collecting coupons is faster with friends. In: <i>Structural Information and Communication Complexity</i>. Vol 12810. Springer Nature; 2021:3-12. doi:<a href=\"https://doi.org/10.1007/978-3-030-79527-6_1\">10.1007/978-3-030-79527-6_1</a>","ieee":"D.-A. Alistarh and P. Davies, “Collecting coupons is faster with friends,” in <i>Structural Information and Communication Complexity</i>, Wrocław, Poland, 2021, vol. 12810, pp. 3–12.","mla":"Alistarh, Dan-Adrian, and Peter Davies. “Collecting Coupons Is Faster with Friends.” <i>Structural Information and Communication Complexity</i>, vol. 12810, Springer Nature, 2021, pp. 3–12, doi:<a href=\"https://doi.org/10.1007/978-3-030-79527-6_1\">10.1007/978-3-030-79527-6_1</a>.","apa":"Alistarh, D.-A., &#38; Davies, P. (2021). Collecting coupons is faster with friends. In <i>Structural Information and Communication Complexity</i> (Vol. 12810, pp. 3–12). Wrocław, Poland: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-79527-6_1\">https://doi.org/10.1007/978-3-030-79527-6_1</a>","short":"D.-A. Alistarh, P. Davies, in:, Structural Information and Communication Complexity, Springer Nature, 2021, pp. 3–12.","ista":"Alistarh D-A, Davies P. 2021. Collecting coupons is faster with friends. Structural Information and Communication Complexity.  SIROCCO: International Colloquium on Structural Information and Communication Complexity, LNCS, vol. 12810, 3–12.","chicago":"Alistarh, Dan-Adrian, and Peter Davies. “Collecting Coupons Is Faster with Friends.” In <i>Structural Information and Communication Complexity</i>, 12810:3–12. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-79527-6_1\">https://doi.org/10.1007/978-3-030-79527-6_1</a>."},"ddc":["000"],"date_published":"2021-06-20T00:00:00Z","month":"06"},{"acknowledgement":"This work is partially supported by a Weizmann-UK Making Connections Grant, the Centre for Discrete Mathematics and its Applications (DIMAP), IBM Faculty Award, EPSRC award EP/V01305X/1, European Research Council (ERC) Grant No. 949083, the Minerva foundation with funding from the Federal German Ministry for Education and Research No. 713238, and the European Union’s Horizon 2020 programme under the Marie Skłodowska-Curie grant agreement No 754411.","title":"Component stability in low-space massively parallel computation","main_file_link":[{"url":"https://arxiv.org/abs/2106.01880","open_access":"1"}],"article_processing_charge":"No","publication":"Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing","language":[{"iso":"eng"}],"year":"2021","date_updated":"2023-08-17T07:11:32Z","citation":{"ama":"Czumaj A, Davies P, Parter M. Component stability in low-space massively parallel computation. In: <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2021:481–491. doi:<a href=\"https://doi.org/10.1145/3465084.3467903\">10.1145/3465084.3467903</a>","ieee":"A. Czumaj, P. Davies, and M. Parter, “Component stability in low-space massively parallel computation,” in <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>, Virtual, Italy, 2021, pp. 481–491.","mla":"Czumaj, Artur, et al. “Component Stability in Low-Space Massively Parallel Computation.” <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2021, pp. 481–491, doi:<a href=\"https://doi.org/10.1145/3465084.3467903\">10.1145/3465084.3467903</a>.","apa":"Czumaj, A., Davies, P., &#38; Parter, M. (2021). Component stability in low-space massively parallel computation. In <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i> (pp. 481–491). Virtual, Italy: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3465084.3467903\">https://doi.org/10.1145/3465084.3467903</a>","short":"A. Czumaj, P. Davies, M. Parter, in:, Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2021, pp. 481–491.","ista":"Czumaj A, Davies P, Parter M. 2021. Component stability in low-space massively parallel computation. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. PODC: Principles of Distributed Computing, 481–491.","chicago":"Czumaj, Artur, Peter Davies, and Merav Parter. “Component Stability in Low-Space Massively Parallel Computation.” In <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>, 481–491. Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3465084.3467903\">https://doi.org/10.1145/3465084.3467903</a>."},"type":"conference","month":"07","date_published":"2021-07-21T00:00:00Z","doi":"10.1145/3465084.3467903","conference":{"location":"Virtual, Italy","start_date":"2021-07-26","name":"PODC: Principles of Distributed Computing","end_date":"2021-07-30"},"ec_funded":1,"oa_version":"Submitted Version","isi":1,"day":"21","department":[{"_id":"DaAl"}],"quality_controlled":"1","arxiv":1,"oa":1,"page":"481–491","publisher":"Association for Computing Machinery","status":"public","date_created":"2021-08-17T18:11:16Z","abstract":[{"text":"In this paper, we study the power and limitations of component-stable algorithms in the low-space model of Massively Parallel Computation (MPC). Recently Ghaffari, Kuhn and Uitto (FOCS 2019) introduced the class of component-stable low-space MPC algorithms, which are, informally, defined as algorithms for which the outputs reported by the nodes in different connected components are required to be independent. This very natural notion was introduced to capture most (if not all) of the known efficient MPC algorithms to date, and it was the first general class of MPC algorithms for which one can show non-trivial conditional lower bounds. In this paper we enhance the framework of component-stable algorithms and investigate its effect on the complexity of randomized and deterministic low-space MPC. Our key contributions include: 1) We revise and formalize the lifting approach of Ghaffari, Kuhn and Uitto. This requires a very delicate amendment of the notion of component stability, which allows us to fill in gaps in the earlier arguments. 2) We also extend the framework to obtain conditional lower bounds for deterministic algorithms and fine-grained lower bounds that depend on the maximum degree Δ. 3) We demonstrate a collection of natural graph problems for which non-component-stable algorithms break the conditional lower bound obtained for component-stable algorithms. This implies that, for both deterministic and randomized algorithms, component-stable algorithms are conditionally weaker than the non-component-stable ones.\r\n\r\nAltogether our results imply that component-stability might limit the computational power of the low-space MPC model, paving the way for improved upper bounds that escape the conditional lower bound setting of Ghaffari, Kuhn, and Uitto.","lang":"eng"}],"_id":"9933","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication_status":"published","author":[{"full_name":"Czumaj, Artur","last_name":"Czumaj","first_name":"Artur"},{"last_name":"Davies","orcid":"0000-0002-5646-9524","first_name":"Peter","id":"11396234-BB50-11E9-B24C-90FCE5697425","full_name":"Davies, Peter"},{"full_name":"Parter, Merav","last_name":"Parter","first_name":"Merav"}],"external_id":{"arxiv":["2106.01880"],"isi":["000744439800049"]},"project":[{"call_identifier":"H2020","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships"}],"publication_identifier":{"isbn":["9781450385480"]}},{"external_id":{"isi":["000744439800048"]},"author":[{"full_name":"Czumaj, Artur","last_name":"Czumaj","first_name":"Artur"},{"orcid":"0000-0002-5646-9524","last_name":"Davies","first_name":"Peter","id":"11396234-BB50-11E9-B24C-90FCE5697425","full_name":"Davies, Peter"},{"first_name":"Merav","last_name":"Parter","full_name":"Parter, Merav"}],"publication_identifier":{"isbn":["978-1-4503-8548-0"]},"project":[{"name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","call_identifier":"H2020"}],"_id":"9935","abstract":[{"text":"We present a deterministic O(log log log n)-round low-space Massively Parallel Computation (MPC) algorithm for the classical problem of (Δ+1)-coloring on n-vertex graphs. In this model, every machine has sublinear local space of size n^φ for any arbitrary constant φ \\in (0,1). Our algorithm works under the relaxed setting where each machine is allowed to perform exponential local computations, while respecting the n^φ space and bandwidth limitations.\r\n\r\nOur key technical contribution is a novel derandomization of the ingenious (Δ+1)-coloring local algorithm by Chang-Li-Pettie (STOC 2018, SIAM J. Comput. 2020). The Chang-Li-Pettie algorithm runs in T_local =poly(loglog n) rounds, which sets the state-of-the-art randomized round complexity for the problem in the local model. Our derandomization employs a combination of tools, notably pseudorandom generators (PRG) and bounded-independence hash functions.\r\n\r\nThe achieved round complexity of O(logloglog n) rounds matches the bound of log(T_local ), which currently serves an upper bound barrier for all known randomized algorithms for locally-checkable problems in this model. Furthermore, no deterministic sublogarithmic low-space MPC algorithms for the (Δ+1)-coloring problem have been known before.","lang":"eng"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication_status":"published","page":"469–479","publisher":"Association for Computing Machinery","status":"public","date_created":"2021-08-17T18:14:15Z","department":[{"_id":"DaAl"}],"isi":1,"day":"21","oa":1,"quality_controlled":"1","ec_funded":1,"conference":{"end_date":"2021-07-30","name":"PODC: Symposium on Principles of Distributed Computing","start_date":"2021-07-26","location":"Virtual, Italy"},"doi":"10.1145/3465084.3467937","oa_version":"Submitted Version","citation":{"short":"A. Czumaj, P. Davies, M. Parter, in:, Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2021, pp. 469–479.","apa":"Czumaj, A., Davies, P., &#38; Parter, M. (2021). Improved deterministic (Δ+1) coloring in low-space MPC. In <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i> (pp. 469–479). Virtual, Italy: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3465084.3467937\">https://doi.org/10.1145/3465084.3467937</a>","chicago":"Czumaj, Artur, Peter Davies, and Merav Parter. “Improved Deterministic (Δ+1) Coloring in Low-Space MPC.” In <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>, 469–479. Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3465084.3467937\">https://doi.org/10.1145/3465084.3467937</a>.","ista":"Czumaj A, Davies P, Parter M. 2021. Improved deterministic (Δ+1) coloring in low-space MPC. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 469–479.","ama":"Czumaj A, Davies P, Parter M. Improved deterministic (Δ+1) coloring in low-space MPC. In: <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2021:469–479. doi:<a href=\"https://doi.org/10.1145/3465084.3467937\">10.1145/3465084.3467937</a>","mla":"Czumaj, Artur, et al. “Improved Deterministic (Δ+1) Coloring in Low-Space MPC.” <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2021, pp. 469–479, doi:<a href=\"https://doi.org/10.1145/3465084.3467937\">10.1145/3465084.3467937</a>.","ieee":"A. Czumaj, P. Davies, and M. Parter, “Improved deterministic (Δ+1) coloring in low-space MPC,” in <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>, Virtual, Italy, 2021, pp. 469–479."},"date_updated":"2023-08-17T07:11:03Z","type":"conference","month":"07","date_published":"2021-07-21T00:00:00Z","article_processing_charge":"No","publication":"Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing","language":[{"iso":"eng"}],"year":"2021","acknowledgement":"This work is partially supported by a Weizmann-UK Making Connections Grant, the Centre for Discrete Mathematics and its Applications (DIMAP), IBM Faculty Award, EPSRC award EP/V01305X/1, European Research Council (ERC) Grant No. 949083, the Minerva foundation with funding from the Federal German Ministry for Education and Research No. 713238, and the European Union’s Horizon 2020 programme under the Marie Skłodowska-Curie grant agreement No 754411.","main_file_link":[{"url":"http://wrap.warwick.ac.uk/153753","open_access":"1"}],"title":"Improved deterministic (Δ+1) coloring in low-space MPC"},{"article_processing_charge":"No","publication":"Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020)","year":"2020","language":[{"iso":"eng"}],"title":"Graph sparsification for derandomizing massively parallel computation with low space","main_file_link":[{"url":"https://arxiv.org/abs/1912.05390","open_access":"1"}],"related_material":{"record":[{"id":"9541","relation":"later_version","status":"public"}]},"conference":{"end_date":"2020-07-17","start_date":"2020-07-15","name":"SPAA: Symposium on Parallelism in Algorithms and Architectures","location":"Virtual Event, United States"},"doi":"10.1145/3350755.3400282","ec_funded":1,"oa_version":"Preprint","date_updated":"2024-02-28T12:53:09Z","citation":{"ama":"Czumaj A, Davies P, Parter M. Graph sparsification for derandomizing massively parallel computation with low space. In: <i>Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020)</i>. Association for Computing Machinery; 2020:175-185. doi:<a href=\"https://doi.org/10.1145/3350755.3400282\">10.1145/3350755.3400282</a>","mla":"Czumaj, Artur, et al. “Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space.” <i>Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020)</i>, no. 7, Association for Computing Machinery, 2020, pp. 175–85, doi:<a href=\"https://doi.org/10.1145/3350755.3400282\">10.1145/3350755.3400282</a>.","ieee":"A. Czumaj, P. Davies, and M. Parter, “Graph sparsification for derandomizing massively parallel computation with low space,” in <i>Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020)</i>, Virtual Event, United States, 2020, no. 7, pp. 175–185.","short":"A. Czumaj, P. Davies, M. Parter, in:, Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020), Association for Computing Machinery, 2020, pp. 175–185.","apa":"Czumaj, A., Davies, P., &#38; Parter, M. (2020). Graph sparsification for derandomizing massively parallel computation with low space. In <i>Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020)</i> (pp. 175–185). Virtual Event, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3350755.3400282\">https://doi.org/10.1145/3350755.3400282</a>","chicago":"Czumaj, Artur, Peter Davies, and Merav Parter. “Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space.” In <i>Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020)</i>, 175–85. Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3350755.3400282\">https://doi.org/10.1145/3350755.3400282</a>.","ista":"Czumaj A, Davies P, Parter M. 2020. Graph sparsification for derandomizing massively parallel computation with low space. Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020). SPAA: Symposium on Parallelism in Algorithms and Architectures, 175–185."},"type":"conference","month":"07","date_published":"2020-07-01T00:00:00Z","scopus_import":"1","publisher":"Association for Computing Machinery","page":"175-185","status":"public","date_created":"2020-05-06T08:53:34Z","isi":1,"day":"01","department":[{"_id":"DaAl"}],"quality_controlled":"1","arxiv":1,"oa":1,"issue":"7","author":[{"last_name":"Czumaj","orcid":"0000-0002-5646-9524","first_name":"Artur","full_name":"Czumaj, Artur"},{"full_name":"Davies, Peter","id":"11396234-BB50-11E9-B24C-90FCE5697425","last_name":"Davies","orcid":"0000-0002-5646-9524","first_name":"Peter"},{"last_name":"Parter","first_name":"Merav","full_name":"Parter, Merav"}],"external_id":{"isi":["000744436200015"],"arxiv":["1912.05390"]},"project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","grant_number":"754411"}],"abstract":[{"text":"The Massively Parallel Computation (MPC) model is an emerging model which distills core  aspects of distributed and parallel computation. It has been developed as a tool to solve (typically graph) problems in systems where the input is distributed over many machines with limited space.\r\n\t\r\nRecent work has focused on the regime in which machines have sublinear (in $n$, the number of nodes in the input graph) space, with randomized algorithms presented for fundamental graph problems of Maximal Matching and Maximal Independent Set. However, there have been no prior corresponding deterministic algorithms.\r\n\t\r\n\tA major challenge underlying the sublinear space setting is that the local space of each machine might be too small to store all the edges incident to a single node. This poses a considerable obstacle compared to the classical models in which each node is assumed to know and have easy access to its incident edges. To overcome this barrier we introduce a new graph sparsification technique that deterministically computes a low-degree subgraph with additional desired properties. The degree of the nodes in this subgraph is small in the sense that the edges of each node can be now stored on a single machine. This low-degree subgraph also has the property that solving the problem on this subgraph provides \\emph{significant} global progress, i.e., progress towards solving the problem for the original input graph.\r\n\t\r\nUsing this framework to derandomize the well-known randomized algorithm of Luby [SICOMP'86], we obtain $O(\\log \\Delta+\\log\\log n)$-round deterministic MPC algorithms for solving the fundamental problems of Maximal Matching and Maximal Independent Set with $O(n^{\\epsilon})$ space on each machine for any constant $\\epsilon > 0$. Based on the recent work of Ghaffari et al. [FOCS'18], this additive $O(\\log\\log n)$ factor is conditionally essential. These algorithms can also be shown to run in $O(\\log \\Delta)$ rounds in the closely related model of CONGESTED CLIQUE, improving upon the state-of-the-art bound of $O(\\log^2 \\Delta)$ rounds by Censor-Hillel et al. [DISC'17].","lang":"eng"}],"_id":"7802","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication_status":"published"},{"oa_version":"Submitted Version","file_date_updated":"2020-10-08T08:17:36Z","doi":"10.1145/3382734.3405751","conference":{"location":"Salerno, Italy","start_date":"2020-08-03","name":"PODC: Symposium on Principles of Distributed Computing","end_date":"2020-08-07"},"ec_funded":1,"ddc":["000"],"date_published":"2020-07-01T00:00:00Z","month":"07","type":"conference","citation":{"mla":"Czumaj, Artur, et al. “Simple, Deterministic, Constant-Round Coloring in the Congested Clique.” <i>Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2020, pp. 309–18, doi:<a href=\"https://doi.org/10.1145/3382734.3405751\">10.1145/3382734.3405751</a>.","ieee":"A. Czumaj, P. Davies, and M. Parter, “Simple, deterministic, constant-round coloring in the congested clique,” in <i>Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing</i>, Salerno, Italy, 2020, pp. 309–318.","ama":"Czumaj A, Davies P, Parter M. Simple, deterministic, constant-round coloring in the congested clique. In: <i>Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2020:309-318. doi:<a href=\"https://doi.org/10.1145/3382734.3405751\">10.1145/3382734.3405751</a>","chicago":"Czumaj, Artur, Peter Davies, and Merav Parter. “Simple, Deterministic, Constant-Round Coloring in the Congested Clique.” In <i>Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing</i>, 309–18. Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3382734.3405751\">https://doi.org/10.1145/3382734.3405751</a>.","ista":"Czumaj A, Davies P, Parter M. 2020. Simple, deterministic, constant-round coloring in the congested clique. Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 309–318.","short":"A. Czumaj, P. Davies, M. Parter, in:, Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2020, pp. 309–318.","apa":"Czumaj, A., Davies, P., &#38; Parter, M. (2020). Simple, deterministic, constant-round coloring in the congested clique. In <i>Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing</i> (pp. 309–318). Salerno, Italy: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3382734.3405751\">https://doi.org/10.1145/3382734.3405751</a>"},"has_accepted_license":"1","date_updated":"2021-01-12T08:15:37Z","language":[{"iso":"eng"}],"year":"2020","article_processing_charge":"No","publication":"Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing","title":"Simple, deterministic, constant-round coloring in the congested clique","project":[{"name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"754411"}],"author":[{"last_name":"Czumaj","orcid":"0000-0002-5646-9524","first_name":"Artur","full_name":"Czumaj, Artur"},{"first_name":"Peter","last_name":"Davies","orcid":"0000-0002-5646-9524","id":"11396234-BB50-11E9-B24C-90FCE5697425","full_name":"Davies, Peter"},{"full_name":"Parter, Merav","first_name":"Merav","last_name":"Parter"}],"external_id":{"arxiv":["2009.06043"]},"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"We settle the complexity of the (Δ+1)-coloring and (Δ+1)-list coloring problems in the CONGESTED CLIQUE model by presenting a simple deterministic algorithm for both problems running in a constant number of rounds. This matches the complexity of the recent breakthrough randomized constant-round (Δ+1)-list coloring algorithm due to Chang et al. (PODC'19), and significantly improves upon the state-of-the-art O(logΔ)-round deterministic (Δ+1)-coloring bound of Parter (ICALP'18).\r\nA remarkable property of our algorithm is its simplicity. Whereas the state-of-the-art randomized algorithms for this problem are based on the quite involved local coloring algorithm of Chang et al. (STOC'18), our algorithm can be described in just a few lines. At a high level, it applies a careful derandomization of a recursive procedure which partitions the nodes and their respective palettes into separate bins. We show that after O(1) recursion steps, the remaining uncolored subgraph within each bin has linear size, and thus can be solved locally by collecting it to a single node. This algorithm can also be implemented in the Massively Parallel Computation (MPC) model provided that each machine has linear (in n, the number of nodes in the input graph) space.\r\nWe also show an extension of our algorithm to the MPC regime in which machines have sublinear space: we present the first deterministic (Δ+1)-list coloring algorithm designed for sublinear-space MPC, which runs in O(logΔ+loglogn) rounds."}],"_id":"7803","date_created":"2020-05-06T09:02:14Z","status":"public","page":"309-318","publisher":"Association for Computing Machinery","file":[{"relation":"main_file","file_id":"8624","file_size":520051,"content_type":"application/pdf","creator":"pdavies","date_updated":"2020-10-08T08:17:36Z","success":1,"checksum":"46fe4fc58a64eb04068115573f631d4c","date_created":"2020-10-08T08:17:36Z","file_name":"ColoringArxiv.pdf","access_level":"open_access"}],"quality_controlled":"1","oa":1,"arxiv":1,"day":"01","department":[{"_id":"DaAl"}]}]