---
_id: '10435'
abstract:
- lang: eng
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.
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"
article_processing_charge: No
arxiv: 1
author:
- first_name: Giorgi
full_name: Nadiradze, Giorgi
id: 3279A00C-F248-11E8-B48F-1D18A9856A87
last_name: Nadiradze
orcid: 0000-0001-5634-0731
- first_name: Amirmojtaba
full_name: Sabour, Amirmojtaba
id: bcc145fd-e77f-11ea-ae8b-80d661dbff67
last_name: Sabour
- first_name: Peter
full_name: Davies, Peter
id: 11396234-BB50-11E9-B24C-90FCE5697425
last_name: Davies
orcid: 0000-0002-5646-9524
- first_name: Shigang
full_name: Li, Shigang
last_name: Li
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
citation:
ama: 'Nadiradze G, Sabour A, Davies P, Li S, Alistarh D-A. Asynchronous decentralized
SGD with quantized and local updates. In: 35th Conference on Neural Information
Processing Systems. Neural Information Processing Systems Foundation; 2021.'
apa: 'Nadiradze, G., Sabour, A., Davies, P., Li, S., & Alistarh, D.-A. (2021).
Asynchronous decentralized SGD with quantized and local updates. In 35th Conference
on Neural Information Processing Systems. Sydney, Australia: Neural Information
Processing Systems Foundation.'
chicago: Nadiradze, Giorgi, Amirmojtaba Sabour, Peter Davies, Shigang Li, and Dan-Adrian
Alistarh. “Asynchronous Decentralized SGD with Quantized and Local Updates.” In
35th Conference on Neural Information Processing Systems. 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 35th Conference on
Neural Information Processing Systems, Sydney, Australia, 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.'
mla: Nadiradze, Giorgi, et al. “Asynchronous Decentralized SGD with Quantized and
Local Updates.” 35th Conference on Neural Information Processing Systems,
Neural Information Processing Systems Foundation, 2021.
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.
conference:
end_date: 2021-12-14
location: Sydney, Australia
name: 'NeurIPS: Neural Information Processing Systems'
start_date: 2021-12-06
date_created: 2021-12-09T10:59:12Z
date_published: 2021-12-01T00:00:00Z
date_updated: 2023-10-17T11:48:56Z
day: '01'
department:
- _id: DaAl
ec_funded: 1
external_id:
arxiv:
- '1910.12308'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://papers.nips.cc/paper/2021/hash/362c99307cdc3f2d8b410652386a9dd1-Abstract.html
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
publication: 35th Conference on Neural Information Processing Systems
publication_status: published
publisher: Neural Information Processing Systems Foundation
quality_controlled: '1'
related_material:
record:
- id: '10429'
relation: dissertation_contains
status: public
status: public
title: Asynchronous decentralized SGD with quantized and local updates
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '11452'
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.
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.
article_processing_charge: No
arxiv: 1
author:
- first_name: Foivos
full_name: Alimisis, Foivos
last_name: Alimisis
- first_name: Peter
full_name: Davies, Peter
id: 11396234-BB50-11E9-B24C-90FCE5697425
last_name: Davies
orcid: 0000-0002-5646-9524
- first_name: Bart
full_name: Vandereycken, Bart
last_name: Vandereycken
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
citation:
ama: 'Alimisis F, Davies P, Vandereycken B, Alistarh D-A. Distributed principal
component analysis with limited communication. In: Advances in Neural Information
Processing Systems - 35th Conference on Neural Information Processing Systems.
Vol 4. Neural Information Processing Systems Foundation; 2021:2823-2834.'
apa: 'Alimisis, F., Davies, P., Vandereycken, B., & Alistarh, D.-A. (2021).
Distributed principal component analysis with limited communication. In Advances
in Neural Information Processing Systems - 35th Conference on Neural Information
Processing Systems (Vol. 4, pp. 2823–2834). Virtual, Online: Neural Information
Processing Systems Foundation.'
chicago: Alimisis, Foivos, Peter Davies, Bart Vandereycken, and Dan-Adrian Alistarh.
“Distributed Principal Component Analysis with Limited Communication.” In Advances
in Neural Information Processing Systems - 35th Conference on Neural Information
Processing Systems, 4:2823–34. Neural Information Processing Systems Foundation,
2021.
ieee: F. Alimisis, P. Davies, B. Vandereycken, and D.-A. Alistarh, “Distributed
principal component analysis with limited communication,” in Advances in Neural
Information Processing Systems - 35th Conference on Neural Information Processing
Systems, Virtual, Online, 2021, vol. 4, pp. 2823–2834.
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.'
mla: Alimisis, Foivos, et al. “Distributed Principal Component Analysis with Limited
Communication.” Advances in Neural Information Processing Systems - 35th Conference
on Neural Information Processing Systems, vol. 4, Neural Information Processing
Systems Foundation, 2021, pp. 2823–34.
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.
conference:
end_date: 2021-12-14
location: Virtual, Online
name: 'NeurIPS: Neural Information Processing Systems'
start_date: 2021-12-06
date_created: 2022-06-19T22:01:58Z
date_published: 2021-12-01T00:00:00Z
date_updated: 2022-06-20T08:31:52Z
day: '01'
department:
- _id: DaAl
ec_funded: 1
external_id:
arxiv:
- '2110.14391'
intvolume: ' 4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://proceedings.neurips.cc/paper/2021/file/1680e9fa7b4dd5d62ece800239bb53bd-Paper.pdf
month: '12'
oa: 1
oa_version: Published Version
page: 2823-2834
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Advances in Neural Information Processing Systems - 35th Conference on
Neural Information Processing Systems
publication_identifier:
isbn:
- '9781713845393'
issn:
- 1049-5258
publication_status: published
publisher: Neural Information Processing Systems Foundation
quality_controlled: '1'
scopus_import: '1'
status: public
title: Distributed principal component analysis with limited communication
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2021'
...
---
_id: '13147'
abstract:
- lang: eng
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."
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.
article_processing_charge: No
arxiv: 1
author:
- first_name: Foivos
full_name: Alimisis, Foivos
last_name: Alimisis
- first_name: Peter
full_name: Davies, Peter
id: 11396234-BB50-11E9-B24C-90FCE5697425
last_name: Davies
orcid: 0000-0002-5646-9524
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
citation:
ama: 'Alimisis F, Davies P, Alistarh D-A. Communication-efficient distributed optimization
with quantized preconditioners. In: Proceedings of the 38th International Conference
on Machine Learning. Vol 139. ML Research Press; 2021:196-206.'
apa: 'Alimisis, F., Davies, P., & Alistarh, D.-A. (2021). Communication-efficient
distributed optimization with quantized preconditioners. In Proceedings of
the 38th International Conference on Machine Learning (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 Proceedings of
the 38th International Conference on Machine Learning, 139:196–206. ML Research
Press, 2021.
ieee: F. Alimisis, P. Davies, and D.-A. Alistarh, “Communication-efficient distributed
optimization with quantized preconditioners,” in Proceedings of the 38th International
Conference on Machine Learning, Virtual, 2021, vol. 139, pp. 196–206.
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.
mla: Alimisis, Foivos, et al. “Communication-Efficient Distributed Optimization
with Quantized Preconditioners.” Proceedings of the 38th International Conference
on Machine Learning, vol. 139, ML Research Press, 2021, pp. 196–206.
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.
conference:
end_date: 2021-07-24
location: Virtual
name: International Conference on Machine Learning
start_date: 2021-07-18
date_created: 2023-06-18T22:00:48Z
date_published: 2021-07-01T00:00:00Z
date_updated: 2023-06-19T10:44:38Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
ec_funded: 1
external_id:
arxiv:
- '2102.07214'
file:
- access_level: open_access
checksum: 7ec0d59bac268b49c76bf2e036dedd7a
content_type: application/pdf
creator: dernst
date_created: 2023-06-19T10:41:05Z
date_updated: 2023-06-19T10:41:05Z
file_id: '13154'
file_name: 2021_PMLR_Alimisis.pdf
file_size: 429087
relation: main_file
success: 1
file_date_updated: 2023-06-19T10:41:05Z
has_accepted_license: '1'
intvolume: ' 139'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '07'
oa: 1
oa_version: Published Version
page: 196-206
project:
- _id: 268A44D6-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '805223'
name: Elastic Coordination for Scalable Machine Learning
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Proceedings of the 38th International Conference on Machine Learning
publication_identifier:
eissn:
- 2640-3498
isbn:
- '9781713845065'
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Communication-efficient distributed optimization with quantized preconditioners
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 139
year: '2021'
...
---
_id: '9541'
abstract:
- lang: eng
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].
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."
article_number: '16'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Artur
full_name: Czumaj, Artur
last_name: Czumaj
- first_name: Peter
full_name: Davies, Peter
id: 11396234-BB50-11E9-B24C-90FCE5697425
last_name: Davies
orcid: 0000-0002-5646-9524
- first_name: Merav
full_name: Parter, Merav
last_name: Parter
citation:
ama: Czumaj A, Davies P, Parter M. Graph sparsification for derandomizing massively
parallel computation with low space. ACM Transactions on Algorithms. 2021;17(2).
doi:10.1145/3451992
apa: Czumaj, A., Davies, P., & Parter, M. (2021). Graph sparsification for derandomizing
massively parallel computation with low space. ACM Transactions on Algorithms.
Association for Computing Machinery. https://doi.org/10.1145/3451992
chicago: Czumaj, Artur, Peter Davies, and Merav Parter. “Graph Sparsification for
Derandomizing Massively Parallel Computation with Low Space.” ACM Transactions
on Algorithms. Association for Computing Machinery, 2021. https://doi.org/10.1145/3451992.
ieee: A. Czumaj, P. Davies, and M. Parter, “Graph sparsification for derandomizing
massively parallel computation with low space,” ACM Transactions on Algorithms,
vol. 17, no. 2. Association for Computing Machinery, 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.
mla: Czumaj, Artur, et al. “Graph Sparsification for Derandomizing Massively Parallel
Computation with Low Space.” ACM Transactions on Algorithms, vol. 17, no.
2, 16, Association for Computing Machinery, 2021, doi:10.1145/3451992.
short: A. Czumaj, P. Davies, M. Parter, ACM Transactions on Algorithms 17 (2021).
date_created: 2021-06-10T19:31:05Z
date_published: 2021-06-01T00:00:00Z
date_updated: 2024-02-28T12:53:09Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1145/3451992
ec_funded: 1
external_id:
arxiv:
- '1912.05390'
isi:
- '000661311300006'
file:
- access_level: open_access
checksum: a21c627683890c309a68f6389302c408
content_type: application/pdf
creator: pdavies
date_created: 2021-06-10T19:33:56Z
date_updated: 2021-06-10T19:33:56Z
file_id: '9542'
file_name: MISMM-arxiv.pdf
file_size: 587404
relation: main_file
success: 1
file_date_updated: 2021-06-10T19:33:56Z
has_accepted_license: '1'
intvolume: ' 17'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1912.05390
month: '06'
oa: 1
oa_version: Submitted Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: ACM Transactions on Algorithms
publication_identifier:
eissn:
- 1549-6333
issn:
- 1549-6325
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '7802'
relation: earlier_version
status: public
status: public
title: Graph sparsification for derandomizing massively parallel computation with
low space
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 17
year: '2021'
...
---
_id: '9543'
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.
article_processing_charge: No
arxiv: 1
author:
- first_name: Peter
full_name: Davies, Peter
id: 11396234-BB50-11E9-B24C-90FCE5697425
last_name: Davies
orcid: 0000-0002-5646-9524
- first_name: Vijaykrishna
full_name: Gurunanthan, Vijaykrishna
last_name: Gurunanthan
- first_name: 'Niusha '
full_name: 'Moshrefi, Niusha '
id: 4db776ff-ce15-11eb-96e3-bc2b90b01c16
last_name: Moshrefi
- first_name: Saleh
full_name: Ashkboos, Saleh
id: 0D0A9058-257B-11EA-A937-9341C3D8BC8A
last_name: Ashkboos
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
citation:
ama: 'Davies P, Gurunanthan V, Moshrefi N, Ashkboos S, Alistarh D-A. New bounds
for distributed mean estimation and variance reduction. In: 9th International
Conference on Learning Representations. ; 2021.'
apa: Davies, P., Gurunanthan, V., Moshrefi, N., Ashkboos, S., & Alistarh, D.-A.
(2021). New bounds for distributed mean estimation and variance reduction. In
9th International Conference on Learning Representations. Virtual.
chicago: Davies, Peter, Vijaykrishna Gurunanthan, Niusha Moshrefi, Saleh Ashkboos,
and Dan-Adrian Alistarh. “New Bounds for Distributed Mean Estimation and Variance
Reduction.” In 9th International Conference on Learning Representations,
2021.
ieee: P. Davies, V. Gurunanthan, N. Moshrefi, S. Ashkboos, and D.-A. Alistarh, “New
bounds for distributed mean estimation and variance reduction,” in 9th International
Conference on Learning Representations, Virtual, 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.'
mla: Davies, Peter, et al. “New Bounds for Distributed Mean Estimation and Variance
Reduction.” 9th International Conference on Learning Representations, 2021.
short: P. Davies, V. Gurunanthan, N. Moshrefi, S. Ashkboos, D.-A. Alistarh, in:,
9th International Conference on Learning Representations, 2021.
conference:
end_date: 2021-05-07
location: Virtual
name: ' ICLR: International Conference on Learning Representations'
start_date: 2021-05-03
date_created: 2021-06-10T19:46:08Z
date_published: 2021-05-01T00:00:00Z
date_updated: 2023-02-23T14:00:40Z
day: '01'
department:
- _id: DaAl
ec_funded: 1
external_id:
arxiv:
- '2002.09268'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://openreview.net/pdf?id=t86MwoUCCNe
month: '05'
oa: 1
oa_version: Published Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 9th International Conference on Learning Representations
publication_status: published
quality_controlled: '1'
status: public
title: New bounds for distributed mean estimation and variance reduction
type: conference
user_id: D865714E-FA4E-11E9-B85B-F5C5E5697425
year: '2021'
...
---
_id: '9620'
abstract:
- lang: eng
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."
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.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Peter
full_name: Davies, Peter
id: 11396234-BB50-11E9-B24C-90FCE5697425
last_name: Davies
orcid: 0000-0002-5646-9524
citation:
ama: 'Alistarh D-A, Davies P. Collecting coupons is faster with friends. In: Structural
Information and Communication Complexity. Vol 12810. Springer Nature; 2021:3-12.
doi:10.1007/978-3-030-79527-6_1'
apa: 'Alistarh, D.-A., & Davies, P. (2021). Collecting coupons is faster with
friends. In Structural Information and Communication Complexity (Vol. 12810,
pp. 3–12). Wrocław, Poland: Springer Nature. https://doi.org/10.1007/978-3-030-79527-6_1'
chicago: Alistarh, Dan-Adrian, and Peter Davies. “Collecting Coupons Is Faster with
Friends.” In Structural Information and Communication Complexity, 12810:3–12.
Springer Nature, 2021. https://doi.org/10.1007/978-3-030-79527-6_1.
ieee: D.-A. Alistarh and P. Davies, “Collecting coupons is faster with friends,”
in Structural Information and Communication Complexity, Wrocław, Poland,
2021, vol. 12810, 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.'
mla: Alistarh, Dan-Adrian, and Peter Davies. “Collecting Coupons Is Faster with
Friends.” Structural Information and Communication Complexity, vol. 12810,
Springer Nature, 2021, pp. 3–12, doi:10.1007/978-3-030-79527-6_1.
short: D.-A. Alistarh, P. Davies, in:, Structural Information and Communication
Complexity, Springer Nature, 2021, pp. 3–12.
conference:
end_date: 2021-07-01
location: Wrocław, Poland
name: ' SIROCCO: International Colloquium on Structural Information and Communication
Complexity'
start_date: 2021-06-28
date_created: 2021-07-01T11:04:43Z
date_published: 2021-06-20T00:00:00Z
date_updated: 2023-02-23T14:02:46Z
day: '20'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1007/978-3-030-79527-6_1
ec_funded: 1
file:
- access_level: open_access
checksum: fe37fb9af3f5016c1084af9d6e7109bd
content_type: application/pdf
creator: pdavies
date_created: 2021-07-01T11:21:40Z
date_updated: 2021-07-01T11:21:40Z
file_id: '9621'
file_name: Population_Coupon_Collector.pdf
file_size: 319728
relation: main_file
file_date_updated: 2021-07-01T11:21:40Z
has_accepted_license: '1'
intvolume: ' 12810'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Preprint
page: 3-12
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Structural Information and Communication Complexity
publication_identifier:
eisbn:
- '9783030795276'
eissn:
- 1611-3349
isbn:
- '9783030795269'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: Collecting coupons is faster with friends
type: conference
user_id: D865714E-FA4E-11E9-B85B-F5C5E5697425
volume: 12810
year: '2021'
...
---
_id: '9933'
abstract:
- lang: eng
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."
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.
article_processing_charge: No
arxiv: 1
author:
- first_name: Artur
full_name: Czumaj, Artur
last_name: Czumaj
- first_name: Peter
full_name: Davies, Peter
id: 11396234-BB50-11E9-B24C-90FCE5697425
last_name: Davies
orcid: 0000-0002-5646-9524
- first_name: Merav
full_name: Parter, Merav
last_name: Parter
citation:
ama: 'Czumaj A, Davies P, Parter M. Component stability in low-space massively parallel
computation. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed
Computing. Association for Computing Machinery; 2021:481–491. doi:10.1145/3465084.3467903'
apa: 'Czumaj, A., Davies, P., & Parter, M. (2021). Component stability in low-space
massively parallel computation. In Proceedings of the 2021 ACM Symposium on
Principles of Distributed Computing (pp. 481–491). Virtual, Italy: Association
for Computing Machinery. https://doi.org/10.1145/3465084.3467903'
chicago: Czumaj, Artur, Peter Davies, and Merav Parter. “Component Stability in
Low-Space Massively Parallel Computation.” In Proceedings of the 2021 ACM Symposium
on Principles of Distributed Computing, 481–491. Association for Computing
Machinery, 2021. https://doi.org/10.1145/3465084.3467903.
ieee: A. Czumaj, P. Davies, and M. Parter, “Component stability in low-space massively
parallel computation,” in Proceedings of the 2021 ACM Symposium on Principles
of Distributed Computing, Virtual, Italy, 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.'
mla: Czumaj, Artur, et al. “Component Stability in Low-Space Massively Parallel
Computation.” Proceedings of the 2021 ACM Symposium on Principles of Distributed
Computing, Association for Computing Machinery, 2021, pp. 481–491, doi:10.1145/3465084.3467903.
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.
conference:
end_date: 2021-07-30
location: Virtual, Italy
name: 'PODC: Principles of Distributed Computing'
start_date: 2021-07-26
date_created: 2021-08-17T18:11:16Z
date_published: 2021-07-21T00:00:00Z
date_updated: 2023-08-17T07:11:32Z
day: '21'
department:
- _id: DaAl
doi: 10.1145/3465084.3467903
ec_funded: 1
external_id:
arxiv:
- '2106.01880'
isi:
- '000744439800049'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2106.01880
month: '07'
oa: 1
oa_version: Submitted Version
page: 481–491
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing
publication_identifier:
isbn:
- '9781450385480'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
status: public
title: Component stability in low-space massively parallel computation
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2021'
...
---
_id: '9935'
abstract:
- lang: eng
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."
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.
article_processing_charge: No
author:
- first_name: Artur
full_name: Czumaj, Artur
last_name: Czumaj
- first_name: Peter
full_name: Davies, Peter
id: 11396234-BB50-11E9-B24C-90FCE5697425
last_name: Davies
orcid: 0000-0002-5646-9524
- first_name: Merav
full_name: Parter, Merav
last_name: Parter
citation:
ama: 'Czumaj A, Davies P, Parter M. Improved deterministic (Δ+1) coloring in low-space
MPC. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed
Computing. Association for Computing Machinery; 2021:469–479. doi:10.1145/3465084.3467937'
apa: 'Czumaj, A., Davies, P., & Parter, M. (2021). Improved deterministic (Δ+1)
coloring in low-space MPC. In Proceedings of the 2021 ACM Symposium on Principles
of Distributed Computing (pp. 469–479). Virtual, Italy: Association for Computing
Machinery. https://doi.org/10.1145/3465084.3467937'
chicago: Czumaj, Artur, Peter Davies, and Merav Parter. “Improved Deterministic
(Δ+1) Coloring in Low-Space MPC.” In Proceedings of the 2021 ACM Symposium
on Principles of Distributed Computing, 469–479. Association for Computing
Machinery, 2021. https://doi.org/10.1145/3465084.3467937.
ieee: A. Czumaj, P. Davies, and M. Parter, “Improved deterministic (Δ+1) coloring
in low-space MPC,” in Proceedings of the 2021 ACM Symposium on Principles of
Distributed Computing, Virtual, Italy, 2021, pp. 469–479.
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.'
mla: Czumaj, Artur, et al. “Improved Deterministic (Δ+1) Coloring in Low-Space MPC.”
Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing,
Association for Computing Machinery, 2021, pp. 469–479, doi:10.1145/3465084.3467937.
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.
conference:
end_date: 2021-07-30
location: Virtual, Italy
name: 'PODC: Symposium on Principles of Distributed Computing'
start_date: 2021-07-26
date_created: 2021-08-17T18:14:15Z
date_published: 2021-07-21T00:00:00Z
date_updated: 2023-08-17T07:11:03Z
day: '21'
department:
- _id: DaAl
doi: 10.1145/3465084.3467937
ec_funded: 1
external_id:
isi:
- '000744439800048'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://wrap.warwick.ac.uk/153753
month: '07'
oa: 1
oa_version: Submitted Version
page: 469–479
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing
publication_identifier:
isbn:
- 978-1-4503-8548-0
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
status: public
title: Improved deterministic (Δ+1) coloring in low-space MPC
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2021'
...
---
_id: '7802'
abstract:
- lang: eng
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]."
article_processing_charge: No
arxiv: 1
author:
- first_name: Artur
full_name: Czumaj, Artur
last_name: Czumaj
orcid: 0000-0002-5646-9524
- first_name: Peter
full_name: Davies, Peter
id: 11396234-BB50-11E9-B24C-90FCE5697425
last_name: Davies
orcid: 0000-0002-5646-9524
- first_name: Merav
full_name: Parter, Merav
last_name: Parter
citation:
ama: 'Czumaj A, Davies P, Parter M. Graph sparsification for derandomizing massively
parallel computation with low space. In: Proceedings of the 32nd ACM Symposium
on Parallelism in Algorithms and Architectures (SPAA 2020). Association for
Computing Machinery; 2020:175-185. doi:10.1145/3350755.3400282'
apa: 'Czumaj, A., Davies, P., & Parter, M. (2020). Graph sparsification for
derandomizing massively parallel computation with low space. In Proceedings
of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA
2020) (pp. 175–185). Virtual Event, United States: Association for Computing
Machinery. https://doi.org/10.1145/3350755.3400282'
chicago: Czumaj, Artur, Peter Davies, and Merav Parter. “Graph Sparsification for
Derandomizing Massively Parallel Computation with Low Space.” In Proceedings
of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA
2020), 175–85. Association for Computing Machinery, 2020. https://doi.org/10.1145/3350755.3400282.
ieee: A. Czumaj, P. Davies, and M. Parter, “Graph sparsification for derandomizing
massively parallel computation with low space,” in Proceedings of the 32nd
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020),
Virtual Event, United States, 2020, no. 7, pp. 175–185.
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.'
mla: Czumaj, Artur, et al. “Graph Sparsification for Derandomizing Massively Parallel
Computation with Low Space.” Proceedings of the 32nd ACM Symposium on Parallelism
in Algorithms and Architectures (SPAA 2020), no. 7, Association for Computing
Machinery, 2020, pp. 175–85, doi:10.1145/3350755.3400282.
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.
conference:
end_date: 2020-07-17
location: Virtual Event, United States
name: 'SPAA: Symposium on Parallelism in Algorithms and Architectures'
start_date: 2020-07-15
date_created: 2020-05-06T08:53:34Z
date_published: 2020-07-01T00:00:00Z
date_updated: 2024-02-28T12:53:09Z
day: '01'
department:
- _id: DaAl
doi: 10.1145/3350755.3400282
ec_funded: 1
external_id:
arxiv:
- '1912.05390'
isi:
- '000744436200015'
isi: 1
issue: '7'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1912.05390
month: '07'
oa: 1
oa_version: Preprint
page: 175-185
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA 2020)
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '9541'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Graph sparsification for derandomizing massively parallel computation with
low space
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2020'
...
---
_id: '7803'
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."
article_processing_charge: No
arxiv: 1
author:
- first_name: Artur
full_name: Czumaj, Artur
last_name: Czumaj
orcid: 0000-0002-5646-9524
- first_name: Peter
full_name: Davies, Peter
id: 11396234-BB50-11E9-B24C-90FCE5697425
last_name: Davies
orcid: 0000-0002-5646-9524
- first_name: Merav
full_name: Parter, Merav
last_name: Parter
citation:
ama: 'Czumaj A, Davies P, Parter M. Simple, deterministic, constant-round coloring
in the congested clique. In: Proceedings of the 2020 ACM Symposium on Principles
of Distributed Computing. Association for Computing Machinery; 2020:309-318.
doi:10.1145/3382734.3405751'
apa: 'Czumaj, A., Davies, P., & Parter, M. (2020). Simple, deterministic, constant-round
coloring in the congested clique. In Proceedings of the 2020 ACM Symposium
on Principles of Distributed Computing (pp. 309–318). Salerno, Italy: Association
for Computing Machinery. https://doi.org/10.1145/3382734.3405751'
chicago: Czumaj, Artur, Peter Davies, and Merav Parter. “Simple, Deterministic,
Constant-Round Coloring in the Congested Clique.” In Proceedings of the 2020
ACM Symposium on Principles of Distributed Computing, 309–18. Association
for Computing Machinery, 2020. https://doi.org/10.1145/3382734.3405751.
ieee: A. Czumaj, P. Davies, and M. Parter, “Simple, deterministic, constant-round
coloring in the congested clique,” in Proceedings of the 2020 ACM Symposium
on Principles of Distributed Computing, Salerno, Italy, 2020, pp. 309–318.
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.'
mla: Czumaj, Artur, et al. “Simple, Deterministic, Constant-Round Coloring in the
Congested Clique.” Proceedings of the 2020 ACM Symposium on Principles of Distributed
Computing, Association for Computing Machinery, 2020, pp. 309–18, doi:10.1145/3382734.3405751.
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.
conference:
end_date: 2020-08-07
location: Salerno, Italy
name: 'PODC: Symposium on Principles of Distributed Computing'
start_date: 2020-08-03
date_created: 2020-05-06T09:02:14Z
date_published: 2020-07-01T00:00:00Z
date_updated: 2021-01-12T08:15:37Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1145/3382734.3405751
ec_funded: 1
external_id:
arxiv:
- '2009.06043'
file:
- access_level: open_access
checksum: 46fe4fc58a64eb04068115573f631d4c
content_type: application/pdf
creator: pdavies
date_created: 2020-10-08T08:17:36Z
date_updated: 2020-10-08T08:17:36Z
file_id: '8624'
file_name: ColoringArxiv.pdf
file_size: 520051
relation: main_file
success: 1
file_date_updated: 2020-10-08T08:17:36Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
page: 309-318
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
status: public
title: Simple, deterministic, constant-round coloring in the congested clique
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2020'
...