Author name cluster

Florent Becker

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

SODA Conference 2025 Conference Paper

Strict Self-Assembly of Discrete Self-Similar Fractals in the abstract Tile Assembly Model

Florent Becker
Daniel Hader
Matthew J. Patitz

This paper answers a long-standing open question in tile-assembly theory, namely that it is possible to strictly assemble discrete self-similar fractals (DSSFs) in the abstract Tile-Assembly Model (aTAM). We prove this in 2 separate ways, each taking advantage of a novel set of tools. One of our constructions shows that specializing the notion of a quine, a program which prints its own output, to the language of tile-assembly naturally induces a fractal structure. The other construction introduces self-describing circuits as a means to abstractly represent the information flow through a tile-assembly construction and shows that such circuits may be constructed for a relative of the Sierpinski carpet, and indeed many other DSSFs, through a process of fixed-point iteration. This later result, or more specifically the machinery used in its construction, further enable us to provide a polynomial time procedure for deciding whether any given subset of ℤ 2 will generate an aTAM producible DSSF. To this end, we also introduce the Tree Pump Theorem, a result analogous to the important Window Movie Lemma, but with requirements on the set of productions rather than on the self-assembling system itself.

Details

I&C Journal 2021 Journal Article

The role of randomness in the broadcast congested clique model

Florent Becker
Pedro Montealegre
Ivan Rapaport
Ioan Todinca

We study the role of randomness in the broadcast congested clique model. This is a message-passing model of distributed computation where the nodes of a network know their local neighborhoods and they broadcast, in synchronous rounds, messages that are visible to every other node. This works aims to separate three different settings: deterministic protocols, randomized protocols with private coins, and randomized protocols with public coins. We obtain the following results: • If more than one round is allowed, public randomness is as powerful as private randomness. • One-round public-coin algorithms can be exponentially more powerful than deterministic algorithms running in several rounds. • One-round public-coin algorithms can be exponentially more powerful than one-round private-coin algorithms. • One-round private-coin algorithms can be exponentially more powerful than one-round deterministic algorithms.

Details DOI

TCS Journal 2010 Journal Article

Average long-lived binary consensus: Quantifying the stabilizing role played by memory

Florent Becker
Sergio Rajsbaum
Ivan Rapaport
Eric Rémila

Consider a system composed of n sensors operating in synchronous rounds. In each round an input vector of sensor readings x is produced, where the i -th entry of x is a binary value produced by the i -th sensor. The sequence of input vectors is assumed to be smooth: exactly one entry of the vector changes from one round to the next one. The system implements a fault-tolerant averaging consensus function f. This function returns, in each round, a representative output value v of the sensor readings x. Assuming that at most t entries of the vector can be erroneous, f is required to return a value that appears at least t + 1 times in x. We introduce the definition of instability of the system, which consists in the number of output changes over a random sequence of input vectors. We first design optimal (with respect to the instability measure) consensus systems: D 0 without memory, and D 1 with memory. Then we quantify the gain factor due to memory by computing c n ( t ), the number of decision changes performed by D 0 per decision change performed by D 1.

Details DOI

TCS Journal 2009 Journal Article

Pictures worth a thousand tiles, a geometrical programming language for self-assembly

Florent Becker

We present a novel way to design self-assembling systems using a notion of signal (or ray) akin to what is used in analyzing the behaviour of cellular automata. This allows purely geometrical constructions, with a smaller specification and easier analysis. We show how to design a system of signals for a given set of shapes, and how to transform these signals into a set of tiles which self-assemble into the desired shapes. We show how to use this technique on two examples: squares (with optimal assembly time and a small number of tiles) and general polygons with arbitrarily good resolution.

Details DOI