3 Search Results for "Coiteux-Roy, Xavier"


Document
Invited Talk
Quantum Distributed Computing: Potential and Limitations (Invited Talk)

Authors: François Le Gall

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)


Abstract
The subject of this talk is quantum distributed computing, i.e., distributed computing where the processors of the network can exchange quantum messages. In the first part of the talk I survey recent results [Taisuke Izumi and François Le Gall, 2019; Taisuke Izumi et al., 2020; François Le Gall and Frédéric Magniez, 2018; François Le Gall et al., 2019; Xudong Wu and Penghui Yao, 2022] and some older results [Michael Ben-Or and Avinatan Hassidim, 2005; Seiichiro Tani et al., 2012] that show the potential of quantum distributed algorithms. In the second part I present our recent work [Xavier Coiteux-Roy et al., 2023] showing the limitations of quantum distributed algorithms for approximate graph coloring. Finally, I mention interesting and important open questions in quantum distributed computing.

Cite as

François Le Gall. Quantum Distributed Computing: Potential and Limitations (Invited Talk). In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{legall:LIPIcs.OPODIS.2023.2,
  author =	{Le Gall, Fran\c{c}ois},
  title =	{{Quantum Distributed Computing: Potential and Limitations}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.2},
  URN =		{urn:nbn:de:0030-drops-194925},
  doi =		{10.4230/LIPIcs.OPODIS.2023.2},
  annote =	{Keywords: Quantum computing, distributed algorithms, CONGEST model, LOCAL model}
}
Document
Sketching the Path to Efficiency: Lightweight Learned Cache Replacement

Authors: Rana Shahout and Roy Friedman

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)


Abstract
Cache management policies are responsible for selecting the items that should be kept in the cache, and are therefore a fundamental design choice for obtaining an effective caching solution. Heuristic approaches have been used to identify access patterns that affect cache management decisions. However, their behavior is inconsistent, as they can perform well for certain access patterns and poorly for others. Given machine learning’s (ML) remarkable achievements in predicting diverse problems, ML techniques can be applied to create a cache management policy. Yet a significant challenge arises from the memory overhead associated with ML components. These components retain per item information and must be invoked on each access, contradicting the goal of minimizing the cache’s resource signature. In this work, we propose ALPS, a light-weight cache management policy that takes into account the cost of the ML component. ALPS combines ML with traditional heuristic-based approaches and facilitates learning by identifying several statistical features derived from space-efficient sketches. ALPS’s ML process derives its features from these sketches, resulting in a lightweight and highly effective meta-policy for cache management. We evaluate our approach over real-world workloads run against five popular heuristic cache management policies as well as a state-of-the-art ML-based policy. In our experiments, ALPS always obtained the best hit ratio. Specifically, ALPS improves the hit ratio compared to LRU by up to 20%, Hyperbolic by up to 31%, ARC by up to 9% and W-TinyLFU by up to 26% on various real-world workloads. Its resource requirements are orders of magnitude lower than previous ML-based approaches.

Cite as

Rana Shahout and Roy Friedman. Sketching the Path to Efficiency: Lightweight Learned Cache Replacement. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 34:1-34:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{shahout_et_al:LIPIcs.OPODIS.2023.34,
  author =	{Shahout, Rana and Friedman, Roy},
  title =	{{Sketching the Path to Efficiency: Lightweight Learned Cache Replacement}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{34:1--34:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.34},
  URN =		{urn:nbn:de:0030-drops-195249},
  doi =		{10.4230/LIPIcs.OPODIS.2023.34},
  annote =	{Keywords: Data streams, Memory Management, Cache Policy, ML}
}
Document
The RGB No-Signalling Game

Authors: Xavier Coiteux-Roy and Claude Crépeau

Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)


Abstract
Introducing the simplest of all No-Signalling Games: the RGB Game where two verifiers interrogate two provers, Alice and Bob, far enough from each other that communication between them is too slow to be possible. Each prover may be independently queried one of three possible colours: Red, Green or Blue. Let a be the colour announced to Alice and b be announced to Bob. To win the game they must reply colours x (resp. y) such that a != x != y != b. This work focuses on this new game mainly as a pedagogical tool for its simplicity but also because it triggered us to introduce a new set of definitions for reductions among multi-party probability distributions and related non-locality classes. We show that a particular winning strategy for the RGB Game is equivalent to the PR-Box of Popescu-Rohrlich and thus No-Signalling. Moreover, we use this example to define No-Signalling in a new useful way, as the intersection of two natural classes of multi-party probability distributions called one-way signalling. We exhibit a quantum strategy able to beat the classical local maximum winning probability of 8/9 shifting it up to 11/12. Optimality of this quantum strategy is demonstrated using the standard tool of semidefinite programming.

Cite as

Xavier Coiteux-Roy and Claude Crépeau. The RGB No-Signalling Game. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{coiteuxroy_et_al:LIPIcs.TQC.2019.4,
  author =	{Coiteux-Roy, Xavier and Cr\'{e}peau, Claude},
  title =	{{The RGB No-Signalling Game}},
  booktitle =	{14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-112-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{135},
  editor =	{van Dam, Wim and Man\v{c}inska, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.4},
  URN =		{urn:nbn:de:0030-drops-103965},
  doi =		{10.4230/LIPIcs.TQC.2019.4},
  annote =	{Keywords: No-Signalling, Quantum Entanglement, Non-Locality, Bell inequality, Semidefinite Programming, Non-locality Hierarchy}
}
  • Refine by Author
  • 1 Coiteux-Roy, Xavier
  • 1 Crépeau, Claude
  • 1 Friedman, Roy
  • 1 Le Gall, François
  • 1 Shahout, Rana

  • Refine by Classification
  • 1 Information systems → Data streams
  • 1 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Quantum computation theory
  • 1 Theory of computation → Quantum information theory

  • Refine by Keyword
  • 1 Bell inequality
  • 1 CONGEST model
  • 1 Cache Policy
  • 1 Data streams
  • 1 LOCAL model
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2024
  • 1 2019

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