Search Results

Documents authored by de Panafieu, Élie

Artifact
Software
DOI: 10.4230/artifacts.22479
torus packing for multisets

Authors: Élie de Panafieu

Abstract
Cite as

Élie de Panafieu. torus packing for multisets (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-22479,
   title = {{torus packing for multisets}}, 
   author = {de Panafieu, \'{E}lie},
   note = {Software, version 1.0., swhId: \href{https://archive.softwareheritage.org/swh:1:dir:2eb591ca09fb8739e2135e17b5f595b7f25ed924;origin=https://gitlab.com/depanafieuelie/torus-packing-for-multisets;visit=swh:1:snp:977c7dfa75b83551f7238790b259989a998825a6;anchor=swh:1:rev:a59cfd49aabd0d6c7eab651836b2ebac621ccf31}{\texttt{swh:1:dir:2eb591ca09fb8739e2135e17b5f595b7f25ed924}} (visited on 2024-11-28)},
   url = {https://gitlab.com/depanafieuelie/torus-packing-for-multisets},
   doi = {10.4230/artifacts.22479},
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.11
Tree Walks and the Spectrum of Random Graphs

Authors: Eva-Maria Hainzl and Élie de Panafieu

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
It is a classic result in spectral theory that the limit distribution of the spectral measure of random graphs G(n,p) converges to the semicircle law in case np tends to infinity with n. The spectral measure for random graphs G(n,c/n) however is less understood. In this work, we combine and extend two combinatorial approaches by Bauer and Golinelli (2001) and Enriquez and Menard (2016) and approximate the moments of the spectral measure by counting walks that span trees.
Cite as

Eva-Maria Hainzl and Élie de Panafieu. Tree Walks and the Spectrum of Random Graphs. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hainzl_et_al:LIPIcs.AofA.2024.11,
  author =	{Hainzl, Eva-Maria and de Panafieu, \'{E}lie},
  title =	{{Tree Walks and the Spectrum of Random Graphs}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.11},
  URN =		{urn:nbn:de:0030-drops-204466},
  doi =		{10.4230/LIPIcs.AofA.2024.11},
  annote =	{Keywords: Spectrum of random matrices, generating functions}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.43
Robot Positioning Using Torus Packing for Multisets

Authors: Chung Shue Chen, Peter Keevash, Sean Kennedy, Élie de Panafieu, and Adrian Vetta

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We consider the design of a positioning system where a robot determines its position from local observations. This is a well-studied problem of considerable practical importance and mathematical interest. The dominant paradigm derives from the classical theory of de Bruijn sequences, where the robot has access to a window within a larger code and can determine its position if these windows are distinct. We propose an alternative model in which the robot has more limited observational powers, which we argue is more realistic in terms of engineering: the robot does not have access to the full pattern of colours (or letters) in the window, but only to the intensity of each colour (or the number of occurrences of each letter). This leads to a mathematically interesting problem with a different flavour to that arising in the classical paradigm, requiring new construction techniques. The parameters of our construction are optimal up to a constant factor, and computing the position requires only a constant number of arithmetic operations.
Cite as

Chung Shue Chen, Peter Keevash, Sean Kennedy, Élie de Panafieu, and Adrian Vetta. Robot Positioning Using Torus Packing for Multisets. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2024.43,
  author =	{Chen, Chung Shue and Keevash, Peter and Kennedy, Sean and de Panafieu, \'{E}lie and Vetta, Adrian},
  title =	{{Robot Positioning Using Torus Packing for Multisets}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{43:1--43:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.43},
  URN =		{urn:nbn:de:0030-drops-201862},
  doi =		{10.4230/LIPIcs.ICALP.2024.43},
  annote =	{Keywords: Universal cycles, positioning systems, de Bruijn sequences}
}
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 About DROPS Imprint Privacy Contact