4 Search Results for "Nolin, Alexandre"

Document
DOI: 10.4230/LIPIcs.DISC.2023.19
Fast Coloring Despite Congested Relays

Authors: Maxime Flin, Magnús M. Halldórsson, and Alexandre Nolin

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
We provide a O(log⁶ log n)-round randomized algorithm for distance-2 coloring in CONGEST with Δ²+1 colors. For Δ≫polylog n, this improves exponentially on the O(logΔ+polylog log n) algorithm of [Halldórsson, Kuhn, Maus, Nolin, DISC'20].
Cite as

Maxime Flin, Magnús M. Halldórsson, and Alexandre Nolin. Fast Coloring Despite Congested Relays. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 19:1-19:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{flin_et_al:LIPIcs.DISC.2023.19,
  author =	{Flin, Maxime and Halld\'{o}rsson, Magn\'{u}s M. and Nolin, Alexandre},
  title =	{{Fast Coloring Despite Congested Relays}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{19:1--19:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.19},
  URN =		{urn:nbn:de:0030-drops-191453},
  doi =		{10.4230/LIPIcs.DISC.2023.19},
  annote =	{Keywords: CONGEST model, distributed graph coloring, power graphs}
}
Document
DOI: 10.4230/LIPIcs.DISC.2022.26
Fast Distributed Vertex Splitting with Applications

Authors: Magnús M. Halldórsson, Yannic Maus, and Alexandre Nolin

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
We present poly log log n-round randomized distributed algorithms to compute vertex splittings, a partition of the vertices of a graph into k parts such that a node of degree d(u) has ≈ d(u)/k neighbors in each part. Our techniques can be seen as the first progress towards general poly log log n-round algorithms for the Lovász Local Lemma. As the main application of our result, we obtain a randomized poly log log n-round CONGEST algorithm for (1+ε)Δ-edge coloring n-node graphs of sufficiently large constant maximum degree Δ, for any ε > 0. Further, our results improve the computation of defective colorings and certain tight list coloring problems. All the results improve the state-of-the-art round complexity exponentially, even in the LOCAL model.
Cite as

Magnús M. Halldórsson, Yannic Maus, and Alexandre Nolin. Fast Distributed Vertex Splitting with Applications. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 26:1-26:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{halldorsson_et_al:LIPIcs.DISC.2022.26,
  author =	{Halld\'{o}rsson, Magn\'{u}s M. and Maus, Yannic and Nolin, Alexandre},
  title =	{{Fast Distributed Vertex Splitting with Applications}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{26:1--26:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.26},
  URN =		{urn:nbn:de:0030-drops-172176},
  doi =		{10.4230/LIPIcs.DISC.2022.26},
  annote =	{Keywords: Graph problems, Edge coloring, List coloring, Lov\'{a}sz local lemma, LOCAL model, CONGEST model, Distributed computing}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.39
Coloring Fast Without Learning Your Neighbors' Colors

Authors: Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus, and Alexandre Nolin

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
We give an improved randomized CONGEST algorithm for distance-2 coloring that uses Δ²+1 colors and runs in O(log n) rounds, improving the recent O(log Δ ⋅ log n)-round algorithm in [Halldórsson, Kuhn, Maus; PODC '20]. We then improve the time complexity to O(log Δ) + 2^{O(√{log log n})}.
Cite as

Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus, and Alexandre Nolin. Coloring Fast Without Learning Your Neighbors' Colors. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 39:1-39:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{halldorsson_et_al:LIPIcs.DISC.2020.39,
  author =	{Halld\'{o}rsson, Magn\'{u}s M. and Kuhn, Fabian and Maus, Yannic and Nolin, Alexandre},
  title =	{{Coloring Fast Without Learning Your Neighbors' Colors}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{39:1--39:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.39},
  URN =		{urn:nbn:de:0030-drops-131170},
  doi =		{10.4230/LIPIcs.DISC.2020.39},
  annote =	{Keywords: distributed graph coloring, distance 2 coloring, congestion}
}
Document
DOI: 10.4230/LIPIcs.TQC.2016.5
Robust Bell Inequalities from Communication Complexity

Authors: Sophie Laplante, Mathieu Laurière, Alexandre Nolin, Jérémie Roland, and Gabriel Senno

Published in: LIPIcs, Volume 61, 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)

Abstract
The question of how large Bell inequality violations can be, for quantum distributions, has been the object of much work in the past several years. We say a Bell inequality is normalized if its absolute value does not exceed 1 for any classical (i.e. local) distribution. Upper and (almost) tight lower bounds have been given in terms of number of outputs of the distribution, number of inputs, and the dimension of the shared quantum states. In this work, we revisit normalized Bell inequalities together with another family: inefficiency-resistant Bell inequalities. To be inefficiency-resistant, the Bell value must not exceed 1 for any local distribution, including those that can abort. Both these families of Bell inequalities are closely related to communication complexity lower bounds. We show how to derive large violations from any gap between classical and quantum communication complexity, provided the lower bound on classical communication is proven using these lower bounds. This leads to inefficiency-resistant violations that can be exponential in the size of the inputs. Finally, we study resistance to noise and inefficiency for these Bell inequalities.
Cite as

Sophie Laplante, Mathieu Laurière, Alexandre Nolin, Jérémie Roland, and Gabriel Senno. Robust Bell Inequalities from Communication Complexity. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 61, pp. 5:1-5:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{laplante_et_al:LIPIcs.TQC.2016.5,
  author =	{Laplante, Sophie and Lauri\`{e}re, Mathieu and Nolin, Alexandre and Roland, J\'{e}r\'{e}mie and Senno, Gabriel},
  title =	{{Robust Bell Inequalities from Communication Complexity}},
  booktitle =	{11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)},
  pages =	{5:1--5:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-019-4},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{61},
  editor =	{Broadbent, Anne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2016.5},
  URN =		{urn:nbn:de:0030-drops-66867},
  doi =		{10.4230/LIPIcs.TQC.2016.5},
  annote =	{Keywords: Communication complexity, Bell inequalities, nonlocality, detector efficiency}
}
  • Refine by Author
  • 4 Nolin, Alexandre
  • 3 Halldórsson, Magnús M.
  • 2 Maus, Yannic
  • 1 Flin, Maxime
  • 1 Kuhn, Fabian
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Distributed algorithms
  • 1 Mathematics of computing → Graph coloring

  • Refine by Keyword
  • 2 CONGEST model
  • 2 distributed graph coloring
  • 1 Bell inequalities
  • 1 Communication complexity
  • 1 Distributed computing
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2016
  • 1 2020
  • 1 2022
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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