12 Search Results for "Becker, Florent"

Document
DOI: 10.4230/LIPIcs.DNA.32.2
Powers and Limitations of Synchronous Self-Assembly: Non-cooperative Assemblies and Limited Synchronization

Authors: Florent Becker, Phillip Drake, Matthew J. Patitz, and Ryder Smith

Published in: LIPIcs, Volume 387, 32nd International Conference on DNA Computing and Molecular Programming (DNA 32) (2026)

Abstract
In abstract models of algorithmic self-assembly, synchronization between attachments has emerged as a crucial distinction between the classical asynchronous model (aTAM) and a new synchronous model, the syncTAM. This paper presents recent advances in gauging the additional power afforded by the syncTAM. While it is known that the syncTAM and the aTAM are each unable to fully simulate the other, this paper offers evidence that the syncTAM is computationally significantly more powerful than the aTAM, especially in the non-cooperative setting. The additional power of the non-cooperative syncTAM is witnessed by the following constructions, all impossible in the non-cooperative aTAM: a flagpole, a strict self-assembly of a variant of the discrete Sierpinski triangle, and the ability to build the same assemblies (modulo scale factor) as directed aTAM systems. The second topic is that of limited synchronization, wherein, when the number of attachments is smaller than some threshold l, they happen synchronously, but attachments in excess of that number must wait. In that context, the precise value of l is crucial, and changes to that value prevent simulation and can change which shapes can be obtained.
Cite as

Florent Becker, Phillip Drake, Matthew J. Patitz, and Ryder Smith. Powers and Limitations of Synchronous Self-Assembly: Non-cooperative Assemblies and Limited Synchronization. In 32nd International Conference on DNA Computing and Molecular Programming (DNA 32). Leibniz International Proceedings in Informatics (LIPIcs), Volume 387, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.DNA.32.2,
  author =	{Becker, Florent and Drake, Phillip and Patitz, Matthew J. and Smith, Ryder},
  title =	{{Powers and Limitations of Synchronous Self-Assembly: Non-cooperative Assemblies and Limited Synchronization}},
  booktitle =	{32nd International Conference on DNA Computing and Molecular Programming (DNA 32)},
  pages =	{2:1--2:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-444-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{387},
  editor =	{Scalise, Dominic and Schweller, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.32.2},
  URN =		{urn:nbn:de:0030-drops-267728},
  doi =		{10.4230/LIPIcs.DNA.32.2},
  annote =	{Keywords: self-assembly, noncooperative self-assembly, models of computation, tile assembly systems}
}
Document
DOI: 10.4230/LIPIcs.DNA.32.3
Shape Reachability in Oritatami Is Complete for P

Authors: Sota Kano and Shinnosuke Seki

Published in: LIPIcs, Volume 387, 32nd International Conference on DNA Computing and Molecular Programming (DNA 32) (2026)

Abstract
RNA co-transcriptional folding is a process in which an RNA sequence, or transcript, folds upon itself while being synthesized nucleotide by nucleotide according to its DNA template. Geary, Rothemund, and Andersen have demonstrated how to program a rectangular tile-like shape into (the DNA template of) an RNA transcript that folds co-transcriptionally into the shape in vitro. Using the oritatami model of co-transcriptional folding, we launch the study on the verification of co-transcriptionally folding systems. Shapes are the primary verification target of practical signification; it is abstracted as a set S of points on the 2D triangular grid. Thus, the shape reachability problem asks if the transcript of a given oritatami system goes through all and only the points in S and halts. We demonstrate a logspace reduction from the circuit value problem (CVP), a well-known P-complete problem, into a subproblem of the shape reachability whose input oritatami system is promised to be deterministic and at delay 3 (abstraction of the relative speed of local optimization to that of transcription), thus concluding that this subproblem DSR(3) is also P-complete. What to be verified may specify not only which points to be visited, but also which route should be taken (path reachability), and, moreover, how abstract nucleotides (beads) along the transcript should bind with each other (conformation reachability). We show that as long as the delay is bounded from above by a constant, the conformation reachability can be solved in logspace, and to this problem, path reachability can be reduced in logspace under the promise that a given oritatami system lets beads form as many bonds as possible (maximum arity).
Cite as

Sota Kano and Shinnosuke Seki. Shape Reachability in Oritatami Is Complete for P. In 32nd International Conference on DNA Computing and Molecular Programming (DNA 32). Leibniz International Proceedings in Informatics (LIPIcs), Volume 387, pp. 3:1-3:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kano_et_al:LIPIcs.DNA.32.3,
  author =	{Kano, Sota and Seki, Shinnosuke},
  title =	{{Shape Reachability in Oritatami Is Complete for P}},
  booktitle =	{32nd International Conference on DNA Computing and Molecular Programming (DNA 32)},
  pages =	{3:1--3:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-444-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{387},
  editor =	{Scalise, Dominic and Schweller, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.32.3},
  URN =		{urn:nbn:de:0030-drops-267737},
  doi =		{10.4230/LIPIcs.DNA.32.3},
  annote =	{Keywords: RNA co-transcriptional folding, Oritatami model, Reachability problems, P-completeness}
}
Artifact
Software
DOI: 10.4230/artifacts.26762
DanielHader/WebTAS

Authors: Daniel Hader

Abstract
Cite as

Daniel Hader. DanielHader/WebTAS (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-25965,
   title = {{DanielHader/WebTAS}}, 
   author = {Hader, Daniel},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:72a3a175c59387141e3c76ee14e7c41c216a0327;origin=https://github.com/DanielHader/WebTAS;visit=swh:1:snp:b41b3ec76f091a67d181ed9098a1833db4f6cd8e;anchor=swh:1:rev:4b83d8eceeb2517e448fed0d3087bf8c5f66f032}{\texttt{swh:1:dir:72a3a175c59387141e3c76ee14e7c41c216a0327}} (visited on 2026-07-01)},
   url = {https://github.com/DanielHader/WebTAS},
   doi = {10.4230/artifacts.26762},
}
Artifact
Software
DOI: 10.4230/artifacts.26763
OnTAS simulator

Authors: Florent Becker and Marie de Sainte Marie

Abstract
Cite as

Florent Becker, Marie de Sainte Marie. OnTAS simulator (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-26763,
   title = {{OnTAS simulator}}, 
   author = {Becker, Florent and de Sainte Marie, Marie},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:59706d65ba40d55deb385105a853b5e36198946f;origin=https://gitlab.aliens-lyon.fr/atam-omninuclear-plr-2025-2026/ontas-simulator.git;visit=swh:1:snp:e7e8fc5d7354e2f0872e44fc49c1d24fac20cfa3;anchor=swh:1:rev:9c1b5f8a077aaab53c3078e246052ba5fb7aa230}{\texttt{swh:1:dir:59706d65ba40d55deb385105a853b5e36198946f}} (visited on 2026-07-01)},
   url = {https://gitlab.aliens-lyon.fr/atam-omninuclear-plr-2025-2026/ontas-simulator},
   doi = {10.4230/artifacts.26763},
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2026.164
Everybody Wants to Be a Seed: Arbitrary Single-Tile Seeds in the Abstract Tile Assembly Model

Authors: Florent Becker and Marie de Sainte Marie

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
Winfree’s abstract Tile Assembly Model (aTAM) is one of the most popular abstract models for DNA nano-computing. This papers presents a seedless version of the aTAM. Instead of a designated seed assembly, any single isolated tile can initiate the assembly. This paper shows that such system can simulate any aTAM system at constant scale and it presents a tile set to do so. All systems can be simulated at scale at most 10 and most of them can be simulated at scale 5, provided that their seeds are large enough. Removing the need for seed in self-assembly is a new way of solving the nucleation problem, that is, the problem of controlling the initialisation of any self-assembly process. It also allows for a convergence of the aTAM towards other classical tiling models, such as Wang’s. The systems presented are based on independent modules made of tiles. The modules are carefully designed so they act kind of like stem cells. When a module self-assembles from an isolated tile, it grows a pseudo-seed which represents the seed of the simulated system with a Hamiltonian cycle along the borders of the corresponding macrotiles. The other modules, which appear later on during the simulation as components of the "regular" macrotiles, depend on each other to self-assemble. In such cases, the assembly is synchronised in a way so that the growth of any pseudo-seed is blocked. This ensures that a macrotile self-assembles only when interacting either with the pseudo-seed or with previously completed macrotiles.
Cite as

Florent Becker and Marie de Sainte Marie. Everybody Wants to Be a Seed: Arbitrary Single-Tile Seeds in the Abstract Tile Assembly Model. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 164:1-164:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.ICALP.2026.164,
  author =	{Becker, Florent and de Sainte Marie, Marie},
  title =	{{Everybody Wants to Be a Seed: Arbitrary Single-Tile Seeds in the Abstract Tile Assembly Model}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{164:1--164:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.164},
  URN =		{urn:nbn:de:0030-drops-265520},
  doi =		{10.4230/LIPIcs.ICALP.2026.164},
  annote =	{Keywords: DNA origami, self-assembly, kinetic modeling, computational modeling, cellular automata}
}
Document
DOI: 10.4230/LIPIcs.DNA.31.8
An Axiomatic Study of Leveraging Blockers to Self-Assemble Arbitrary Shapes via Temperature Programming

Authors: Matthew J. Patitz and Trent A. Rogers

Published in: LIPIcs, Volume 347, 31st International Conference on DNA Computing and Molecular Programming (DNA 31) (2025)

Abstract
In this paper we present a theoretical design for tile-based self-assembling systems where individual tile sets that are universal for various tasks (e.g. building shapes or encoding arbitrary data for algorithmic systems) can be provided their input solely using sequences of variations in temperatures. Although there is prior theoretical work in so-called "temperature programming," the results presented here are based upon recent experimental work with "blocked tiles" that provides plausible evidence for their practical implementation. We develop and present an abstract mathematical model, the BlockTAM, for such systems that is based upon the experimental work, and provide constructions within it for universal number encoding systems and a universal shape building construction. These results mirror previous results in temperature programming, covering the two ends of the spectrum that seek to balance the scale factors of assemblies with the number of temperature phases required, while leveraging the features of the BlockTAM that we hope provide a pathway for future experimental implementations.
Cite as

Matthew J. Patitz and Trent A. Rogers. An Axiomatic Study of Leveraging Blockers to Self-Assemble Arbitrary Shapes via Temperature Programming. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{patitz_et_al:LIPIcs.DNA.31.8,
  author =	{Patitz, Matthew J. and Rogers, Trent A.},
  title =	{{An Axiomatic Study of Leveraging Blockers to Self-Assemble Arbitrary Shapes via Temperature Programming}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.8},
  URN =		{urn:nbn:de:0030-drops-238574},
  doi =		{10.4230/LIPIcs.DNA.31.8},
  annote =	{Keywords: DNA tiles, self-assembly, temperature programming}
}
Document
DOI: 10.4230/LIPIcs.DNA.31.9
Synchronous Versus Asynchronous Tile-Based Self-Assembly

Authors: Florent Becker, Phillip Drake, Matthew J. Patitz, and Trent A. Rogers

Published in: LIPIcs, Volume 347, 31st International Conference on DNA Computing and Molecular Programming (DNA 31) (2025)

Abstract
In this paper we study the relationship between mathematical models of tile-based self-assembly which differ in terms of the synchronicity of tile additions. In the standard abstract Tile Assembly Model (aTAM), each step of assembly consists of a single tile being added to an assembly. At any given time, each location on the perimeter of an assembly to which a tile can legally bind is called a frontier location, and for each step of assembly one frontier location is randomly selected and a tile is added. In the Synchronous Tile Assembly Model (syncTAM), at each step of assembly every frontier location simultaneously receives a tile. Our results show that while directed, non-cooperative syncTAM systems are capable of universal computation (while directed, non-cooperative aTAM systems are known not to be), and they are capable of building shapes that can't be built within the aTAM, the non-cooperative aTAM is also capable of building shapes that can't be built within the syncTAM even cooperatively. We show a variety of results that demonstrate the similarities and differences between these two models.
Cite as

Florent Becker, Phillip Drake, Matthew J. Patitz, and Trent A. Rogers. Synchronous Versus Asynchronous Tile-Based Self-Assembly. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.DNA.31.9,
  author =	{Becker, Florent and Drake, Phillip and Patitz, Matthew J. and Rogers, Trent A.},
  title =	{{Synchronous Versus Asynchronous Tile-Based Self-Assembly}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{9:1--9:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.9},
  URN =		{urn:nbn:de:0030-drops-238580},
  doi =		{10.4230/LIPIcs.DNA.31.9},
  annote =	{Keywords: self-assembly, noncooperative self-assembly, models of computation, tile assembly systems}
}
Document
DOI: 10.4230/LIPIcs.CP.2025.28
SLS-Enhanced Core-Boosted Linear Search for Anytime Maximum Satisfiability

Authors: Ole Lübke and Jeremias Berg

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

Abstract
Maximum Satisfiability (MaxSAT), the constraint paradigm of minimizing a linear expression over Boolean (0-1) variables subject to a set of propositional clauses, is today used for solving NP-hard combinatorial optimization problems in various domains. Especially anytime MaxSAT solvers that compute low-cost solutions within a limited available computational time have significantly improved in recent years. Such solvers can be divided into SAT-based methods that use sophisticated reasoning, and stochastic local search (SLS) methods that heuristically explore the search space. The two are complementary; roughly speaking, SLS struggles with finding feasible solutions, and SAT-based methods with minimizing cost. Consequently, most state-of-the-art anytime MaxSAT solvers run SLS before a SAT-based algorithm with minimal communication between the two. In this paper, we aim to harness the complementary strengths of SAT-based, and SLS approaches in the context of anytime MaxSAT. More precisely, we describe several ways to enhance the performance of the so-called core-boosted linear search algorithm for anytime MaxSAT with SLS techniques. Core-boosted linear search is a three-phase algorithm where each phase uses different types of reasoning. Beyond MaxSAT, core-boosted search has also been successful in the related paradigms of pseudo-boolean optimization and constraint programming. We describe how an SLS approach to MaxSAT can be tightly integrated with all three phases of the algorithm, resulting in non-trivial information exchange in both directions between the SLS algorithm and the reasoning methods. We evaluate our techniques on standard benchmarks from the latest MaxSAT Evaluation and demonstrate that our techniques can noticeably improve on implementations of core-boosted search and SLS.
Cite as

Ole Lübke and Jeremias Berg. SLS-Enhanced Core-Boosted Linear Search for Anytime Maximum Satisfiability. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lubke_et_al:LIPIcs.CP.2025.28,
  author =	{L\"{u}bke, Ole and Berg, Jeremias},
  title =	{{SLS-Enhanced Core-Boosted Linear Search for Anytime Maximum Satisfiability}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{28:1--28:20},
  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.28},
  URN =		{urn:nbn:de:0030-drops-238897},
  doi =		{10.4230/LIPIcs.CP.2025.28},
  annote =	{Keywords: Maximum Satisfiability, MaxSAT, SAT, SLS, Anytime Optimization}
}
Document
DOI: 10.4230/LIPIcs.SAND.2025.14
Fractals in Seeded Tile Automata

Authors: Asher Haun, Ryan Knobel, Adrian Salinas, Ramiro Santos, Robert Schweller, and Tim Wylie

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
This work fully characterizes fractal generation in the seeded Tile Automata model (seeded TA), a model similar to the abstract Tile Assembly model (aTAM) with the added ability for adjacent tiles to change states. Under these assumptions, we first show that all discrete self-similar fractals (DSSFs) with feasible generators are strictly buildable at scale 1 and temperature 1 in seeded TA. We then show that these results imply the existence of a single seeded TA system Γ that can strictly build any DSSF infinitely at scale 1 and temperature 1.
Cite as

Asher Haun, Ryan Knobel, Adrian Salinas, Ramiro Santos, Robert Schweller, and Tim Wylie. Fractals in Seeded Tile Automata. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{haun_et_al:LIPIcs.SAND.2025.14,
  author =	{Haun, Asher and Knobel, Ryan and Salinas, Adrian and Santos, Ramiro and Schweller, Robert and Wylie, Tim},
  title =	{{Fractals in Seeded Tile Automata}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.14},
  URN =		{urn:nbn:de:0030-drops-230677},
  doi =		{10.4230/LIPIcs.SAND.2025.14},
  annote =	{Keywords: self-assembly, tile automata, fractals}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.48
Subshifts Defined by Nondeterministic and Alternating Plane-Walking Automata

Authors: Benjamin Hellouin de Menibus and Pacôme Perrotin

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
Plane-walking automata were introduced by Salo & Törma to recognise languages of two-dimensional infinite words (subshifts), the counterpart of 4-way finite automata for two-dimensional finite words. We extend the model to allow for nondeterminism and alternation of quantifiers. We prove that the recognised subshifts form a strict subclass of sofic subshifts, and that the classes corresponding to existential and universal nondeterminism are incomparable and both larger that the deterministic class. We define a hierarchy of subshifts recognised by plane-walking automata with alternating quantifiers, which we conjecture to be strict.
Cite as

Benjamin Hellouin de Menibus and Pacôme Perrotin. Subshifts Defined by Nondeterministic and Alternating Plane-Walking Automata. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 48:1-48:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hellouindemenibus_et_al:LIPIcs.STACS.2025.48,
  author =	{Hellouin de Menibus, Benjamin and Perrotin, Pac\^{o}me},
  title =	{{Subshifts Defined by Nondeterministic and Alternating Plane-Walking Automata}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{48:1--48:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.48},
  URN =		{urn:nbn:de:0030-drops-228540},
  doi =		{10.4230/LIPIcs.STACS.2025.48},
  annote =	{Keywords: Formal languages, Finite automata, Subshifts, Symbolic dynamics, Tilings}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.34
Quantum Simultaneous Protocols Without Public Coins Using Modified Equality Queries

Authors: François Le Gall, Oran Nadler, Harumichi Nishimura, and Rotem Oshman

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
In this paper we study a quantum version of the multiparty simultaneous message-passing (SMP) model, and we show that in some cases, quantum communication can replace public randomness, even with no entanglement between the parties. This was already known for two players, but not for more than two players, and indeed, so far all that was known was a negative result. Our main technical contribution is a compiler that takes any classical public-coin simultaneous protocol based on "modified equality queries," and converts it into a quantum simultaneous protocol without public coins with roughly the same communication complexity. We then use our compiler to derive protocols for several problems, including frequency moments, neighborhood diversity, enumeration of isolated cliques, and more.
Cite as

François Le Gall, Oran Nadler, Harumichi Nishimura, and Rotem Oshman. Quantum Simultaneous Protocols Without Public Coins Using Modified Equality Queries. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 34:1-34:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{legall_et_al:LIPIcs.OPODIS.2024.34,
  author =	{Le Gall, Fran\c{c}ois and Nadler, Oran and Nishimura, Harumichi and Oshman, Rotem},
  title =	{{Quantum Simultaneous Protocols Without Public Coins Using Modified Equality Queries}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{34:1--34:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.34},
  URN =		{urn:nbn:de:0030-drops-225701},
  doi =		{10.4230/LIPIcs.OPODIS.2024.34},
  annote =	{Keywords: SMP model, multi-party communication, quantum distributed algorithms}
}
Document
DOI: 10.4230/LIPIcs.DNA.29.2
DNA Tile Self-Assembly for 3D-Surfaces: Towards Genus Identification

Authors: Florent Becker and Shahrzad Heydarshahi

Published in: LIPIcs, Volume 276, 29th International Conference on DNA Computing and Molecular Programming (DNA 29) (2023)

Abstract
We introduce a new DNA tile self-assembly model: the Surface Flexible Tile Assembly Model (SFTAM), where 2D tiles are placed on host 3D surfaces made of axis-parallel unit cubes glued together by their faces, called polycubes. The bonds are flexible, so that the assembly can bind on the edges of the polycube. We are interested in the study of SFTAM self-assemblies on 3D surfaces which are not always embeddable in the Euclidean plane, in order to compare their different behaviors and to compute the topological properties of the host surfaces. We focus on a family of polycubes called order-1 cuboids. Order-0 cuboids are polycubes that have six rectangular faces, and order-1 cuboids are made from two order-0 cuboids by substracting one from the other. Thus, order-1 cuboids can be of genus 0 or of genus 1 (then they contain a tunnel). We are interested in the genus of these structures, and we present a SFTAM tile assembly system that determines the genus of a given order-1 cuboid. The SFTAM tile assembly system which we design, contains a specific set Y of tile types with the following properties. If the assembly is made on a host order-1 cuboid C of genus 0, no tile of Y appears in any producible assembly, but if C has genus 1, every terminal assembly contains at least one tile of Y. Thus, for order-1 cuboids our system is able to distinguish the host surfaces according to their genus, by the tiles used in the assembly. This system is specific to order-1 cuboids but we can expect the techniques we use to be generalizable to other families of shapes.
Cite as

Florent Becker and Shahrzad Heydarshahi. DNA Tile Self-Assembly for 3D-Surfaces: Towards Genus Identification. In 29th International Conference on DNA Computing and Molecular Programming (DNA 29). Leibniz International Proceedings in Informatics (LIPIcs), Volume 276, pp. 2:1-2:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.DNA.29.2,
  author =	{Becker, Florent and Heydarshahi, Shahrzad},
  title =	{{DNA Tile Self-Assembly for 3D-Surfaces: Towards Genus Identification}},
  booktitle =	{29th International Conference on DNA Computing and Molecular Programming (DNA 29)},
  pages =	{2:1--2:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-297-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{276},
  editor =	{Chen, Ho-Lin and Evans, Constantine G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.29.2},
  URN =		{urn:nbn:de:0030-drops-187851},
  doi =		{10.4230/LIPIcs.DNA.29.2},
  annote =	{Keywords: Tile self-assembly, DNA computing, Geometric surfaces}
}
  • Refine by Type
  • 10 Document/PDF
  • 6 Document/HTML
  • 2 Artifact

  • Refine by Publication Year
  • 5 2026
  • 6 2025
  • 1 2023

  • Refine by Author
  • 5 Becker, Florent
  • 3 Patitz, Matthew J.
  • 2 Drake, Phillip
  • 2 Rogers, Trent A.
  • 2 de Sainte Marie, Marie
  • Show More...

  • Refine by Series/Journal
  • 10 LIPIcs

  • Refine by Classification
  • 5 Theory of computation → Models of computation
  • 1 Applied computing → Bioinformatics
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Theory of computation
  • 1 Theory of computation → Automata over infinite objects
  • Show More...

  • Refine by Keyword
  • 5 self-assembly
  • 2 models of computation
  • 2 noncooperative self-assembly
  • 2 tile assembly systems
  • 1 Anytime Optimization
  • Show More...

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