Search Results

Documents authored by Robert, Léo

Document
DOI: 10.4230/LIPIcs.FUN.2026.16
Lozenge Tiling by Computing Distances

Authors: Jean-Marie Favreau, Yan Gerard, Pascal Lafourcade, and Léo Robert

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
The Calisson puzzle is a recent tiling game in which one must tile a triangular grid inside a hexagon with lozenges, under the constraint that certain prescribed edges must remain tile boundaries and that adjacent lozenges along these edges have different orientations. We present the first polynomial-time algorithm for this problem, with running time O(n³) for a hexagon of side length n. This algorithm, called the advancing surface algorithm, can be executed in a simple and intuitive way, even by hand with a pencil and an eraser. Its apparent simplicity conceals a deeper algorithmic reinterpretation of the classical ideas of John Conway and William Thurston, which we revisit from a theoretical computer science perspective. We introduce a graph-theoretic and difference constraints overlay that complements Thurston’s theory of lozenge tilings, revealing its intrinsic algorithmic structure and extending its scope to tiling problems with interior constraints and without necessarily boundary conditions. In Thurston’s approach, lozenge tilings are lifted to monotone stepped surfaces in the three-dimensional cubic lattice and projected back to the plane using height functions, reducing the tiling problem to the computation of heights. We show that, at an algorithmic level, selecting a monotone surface corresponds to selecting a directed cut (dicut) in a periodic directed graph, while height functions are solutions of a system of difference constraints. In this formulation, a region is tilable if and only if the associated weighted directed graph contains no cycle of strictly negative total weight. This new graph layer completing Thurston’s theory shows that Bellman–Ford’s shortest path algorithm is the only algorithmic primitive needed to decide feasibility and compute solutions. In particular, our framework allows us to decide whether the infinite triangular grid can be tiled while respecting a finite set of prescribed local constraints, a setting in which no boundary conditions are available.
Cite as

Jean-Marie Favreau, Yan Gerard, Pascal Lafourcade, and Léo Robert. Lozenge Tiling by Computing Distances. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{favreau_et_al:LIPIcs.FUN.2026.16,
  author =	{Favreau, Jean-Marie and Gerard, Yan and Lafourcade, Pascal and Robert, L\'{e}o},
  title =	{{Lozenge Tiling by Computing Distances}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{16:1--16:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.16},
  URN =		{urn:nbn:de:0030-drops-257350},
  doi =		{10.4230/LIPIcs.FUN.2026.16},
  annote =	{Keywords: Tiling, Lozenge, Directed Graph, Dicut, Difference Constraints, Bellman-Ford}
}
Document
DOI: 10.4230/LIPIcs.FUN.2026.33
When Locality Implies Globality: Card-Based ZKP Protocol for Shakashaka Puzzle

Authors: Daiki Miyahara, Léo Robert, Pascal Lafourcade, and Shohei Kaneko

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
Shakashaka is an NP-complete Nikoli puzzle that requires to draw white rectangles by filling a grid with black triangles. Verifying that there are only rectangles drawn in the solution was an open problem for card-based ZKP protocols designers. In this paper, we construct a card-based ZKP protocol to show that a prover can prove to a verifier that he knows a solution of this puzzle without revealing any information. For doing this we prove a local property on all possible 2 × 2 subgrids drawn according to the rules of the game and such configurations are possible valid shapes for rectangles. This local property implies a global property on the shape of the constructed areas. Thanks to this local result for all 2 × 2 subgrids, we are able to establish that the only possible shape in the global grid are rectangles. We also verify other classical rules of Shakashaka.
Cite as

Daiki Miyahara, Léo Robert, Pascal Lafourcade, and Shohei Kaneko. When Locality Implies Globality: Card-Based ZKP Protocol for Shakashaka Puzzle. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{miyahara_et_al:LIPIcs.FUN.2026.33,
  author =	{Miyahara, Daiki and Robert, L\'{e}o and Lafourcade, Pascal and Kaneko, Shohei},
  title =	{{When Locality Implies Globality: Card-Based ZKP Protocol for Shakashaka Puzzle}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.33},
  URN =		{urn:nbn:de:0030-drops-257525},
  doi =		{10.4230/LIPIcs.FUN.2026.33},
  annote =	{Keywords: Card-based cryptography, ShakaShaka, Nikoli, ZKP}
}
Artifact
Software
DOI: 10.4230/artifacts.23375
SAT_for_UNISON

Authors: Asma Khoualdia, Sami Cherif, Stéphane Devismes, and Léo Robert

Abstract
Cite as

Asma Khoualdia, Sami Cherif, Stéphane Devismes, Léo Robert. SAT_for_UNISON (Software, Source Code and Benchmarks). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23375,
   title = {{SAT\underlinefor\underlineUNISON}}, 
   author = {Khoualdia, Asma and Cherif, Sami and Devismes, St\'{e}phane and Robert, L\'{e}o},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:4bc78d189155024f85110cb2dc9ae4aeb470d8bf;origin=https://github.com/asmakhoualdia98/SU_SAT_Exec;visit=swh:1:snp:af5a3ce14a7b5fdca4086ba55a5d21370fe4d3cb;anchor=swh:1:rev:6905da4a2f2dd404ea072c647393ba1f58ba0b4c}{\texttt{swh:1:dir:4bc78d189155024f85110cb2dc9ae4aeb470d8bf}} (visited on 2025-08-08)},
   url = {https://github.com/asmakhoualdia98/SU_SAT_Exec},
   doi = {10.4230/artifacts.23375},
}
Document
DOI: 10.4230/LIPIcs.CP.2025.19
Analyzing Self-Stabilization of Synchronous Unison via Propositional Satisfiability

Authors: Asma Khoualdia, Sami Cherif, Stéphane Devismes, and Léo Robert

Published in: LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025)

Abstract
Synchronous unison is a classical clock synchronization problem in distributed computing, and especially in self-stabilization. This paper explores the self-stabilization of a synchronous unison algorithm proposed by Arora et al. using a propositional satisfiability-based approach. We give a logical formulation of the algorithm. This formulation includes the uniqueness of clock values at each node, the updates of clocks based on the minimum clock value in the neighborhood, and the detection of convergence or divergence. To optimize the models, additional constraints are introduced to reduce redundant cases of initial configurations to be analyzed. Our approach not only verifies the algorithm’s behaviour but also offers insights into enhancing its robustness and applicability to broader distributed systems.
Cite as

Asma Khoualdia, Sami Cherif, Stéphane Devismes, and Léo Robert. Analyzing Self-Stabilization of Synchronous Unison via Propositional Satisfiability. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 19:1-19:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{khoualdia_et_al:LIPIcs.CP.2025.19,
  author =	{Khoualdia, Asma and Cherif, Sami and Devismes, St\'{e}phane and Robert, L\'{e}o},
  title =	{{Analyzing Self-Stabilization of Synchronous Unison via Propositional Satisfiability}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{19:1--19:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-380-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{340},
  editor =	{de la Banda, Maria Garcia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.19},
  URN =		{urn:nbn:de:0030-drops-238806},
  doi =		{10.4230/LIPIcs.CP.2025.19},
  annote =	{Keywords: Self-stabilization, Synchronous Unison, Satisfiability}
}
Document
DOI: 10.4230/LIPIcs.FUN.2021.20
Card-Based ZKP Protocols for Takuzu and Juosan

Authors: Daiki Miyahara, Léo Robert, Pascal Lafourcade, So Takeshige, Takaaki Mizuki, Kazumasa Shinagawa, Atsuki Nagao, and Hideaki Sone

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
Takuzu and Juosan are logical Nikoli games in the spirit of Sudoku. In Takuzu, a grid must be filled with 0’s and 1’s under specific constraints. In Juosan, the grid must be filled with vertical and horizontal dashes with specific constraints. We give physical algorithms using cards to realize zero-knowledge proofs for those games. The goal is to allow a player to show that he/she has the solution without revealing it. Previous work on Takuzu showed a protocol with multiple instances needed. We propose two improvements: only one instance needed and a soundness proof. We also propose a similar proof for Juosan game.
Cite as

Daiki Miyahara, Léo Robert, Pascal Lafourcade, So Takeshige, Takaaki Mizuki, Kazumasa Shinagawa, Atsuki Nagao, and Hideaki Sone. Card-Based ZKP Protocols for Takuzu and Juosan. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 20:1-20:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{miyahara_et_al:LIPIcs.FUN.2021.20,
  author =	{Miyahara, Daiki and Robert, L\'{e}o and Lafourcade, Pascal and Takeshige, So and Mizuki, Takaaki and Shinagawa, Kazumasa and Nagao, Atsuki and Sone, Hideaki},
  title =	{{Card-Based ZKP Protocols for Takuzu and Juosan}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{20:1--20:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.20},
  URN =		{urn:nbn:de:0030-drops-127817},
  doi =		{10.4230/LIPIcs.FUN.2021.20},
  annote =	{Keywords: Zero-knowledge proof, Card-based cryptography, Takuzu, Juosan}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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