Arrow Research search

Author name cluster

Nicolas Schabanel

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.

13 papers
2 author rows

Possible papers

13

MFCS Conference 2016 Conference Paper

Programming Biomolecules That Fold Greedily During Transcription

  • Cody W. Geary
  • Pierre-Étienne Meunier
  • Nicolas Schabanel
  • Shinnosuke Seki 0001

We introduce and study the computational power of Oritatami, a theoretical model to explore greedy molecular folding, by which a molecule begins to fold before awaiting the end of its production. This model is inspired by a recent experimental work demonstrating the construction of shapes at the nanoscale by folding an RNA molecule during its transcription from an engineered sequence of synthetic DNA. An important challenge of this model, also encountered in experiments, is to get a single sequence to fold into different shapes, depending on the surrounding molecules. Another big challenge is that not all parts of the sequence are meaningful for all possible inputs. Hence, to prevent them from interfering with subsequent operations in the Oritatami folding pathway we must structure the unused portions of the sequence depending on the context in which it folds. Next, we introduce general design techniques to solve these challenges and program molecules. Our main result in this direction is an algorithm that is time linear in the sequence length that finds a rule for folding the sequence deterministically into a prescribed set of shapes, dependent on its local environment. This shows that the corresponding problem is fixed-parameter tractable, although we also prove it NP-complete in the number of possible environments.

Details

STOC Conference 2011 Conference Paper

Optimal path search in small worlds: dimension matters

  • George Giakkoupis
  • Nicolas Schabanel

We consider Kleinberg's celebrated small-world model (2000). This model is based on a d-dimensional grid graph of n nodes, augmented by a constant number of "long-range links" per node. It is known that this graph has diameter O(log n), and that a simple greedy search algorithm visits an expected number of O(log 2 n) nodes, which is asymptotically optimal over all decentralized search algorithms. Besides the number of nodes visited, a relevant measure is the length of the path constructed by the search algorithm. A decentralized algorithm by Lebhar and Schabanel (2003) constructs paths of expected length O(log n (loglog n) 2 ) by visiting the same number of nodes as greedy search. A natural question, posed by Kleinberg (2006), is whether there are decentralized algorithms that construct paths of length O(log n) while visiting only a poly-logarithmic number of nodes.

Details

TCS Journal 2009 Journal Article

Progresses in the analysis of stochastic 2D cellular automata: A study of asynchronous 2D minority

  • Damien Regnault
  • Nicolas Schabanel
  • Éric Thierry

Cellular automata are often used to model systems in physics, social sciences, biology that are inherently asynchronous. Over the past 20 years, studies have demonstrated that the behavior of cellular automata drastically changes under asynchronous updates. Still, the few mathematical analyses of asynchronism focus on 1D probabilistic cellular automata, either on single examples or on specific classes. As for other classic dynamical systems in physics, extending known methods from 1D to 2D systems is a long lasting challenging problem. In this paper, we address the problem of analyzing an apparently simple 2D asynchronous cellular automaton: 2D Minority where each cell, when fired, updates to the minority state of its neighborhood. Our simulations reveal that in spite of its simplicity, the minority rule exhibits a quite complex response to asynchronism. By focusing on the fully asynchronous regime, we are however able to describe completely the asymptotic behavior of this dynamics as long as the initial configuration satisfies some natural constraints. Besides these technical results, we have strong reasons to believe that our techniques relying on defining an energy function from the transition table of the automaton may be extended to the wider class of threshold automata. 2 2 An abstract version of this paper has been published in [D. Regnault, N. Schabanel, É. Thierry, Progresses in the analysis of stochastic 2D cellular automata: A study of asynchronous 2D minority, in: LNCS Proc. of 32nd Symp. of Mathematical Foundations of Computer Science, MFCS, vol. 4708, Springer, 2007, pp. 320–332].

Details DOI

MFCS Conference 2007 Conference Paper

Progresses in the Analysis of Stochastic 2D Cellular Automata: A Study of Asynchronous 2D Minority

  • Damien Regnault
  • Nicolas Schabanel
  • Eric Thierry

Abstract Cellular automata are often used to model systems in physics, social sciences, biology that are inherently asynchronous. Over the past 20 years, studies have demonstrated that the behavior of cellular automata drastically changed under asynchronous updates. Still, the few mathematical analyses of asynchronism focus on one-dimensional probabilistic cellular automata, either on single examples or on specific classes. As for other classic dynamical systems in physics, extending known methods from one- to two-dimensional systems is a long lasting challenging problem. In this paper, we address the problem of analysing an apparently simple 2D asynchronous cellular automaton: 2D Minority where each cell, when fired, updates to the minority state of its neighborhood. Our experiments reveal that in spite of its simplicity, the minority rule exhibits a quite complex response to asynchronism. By focusing on the fully asynchronous regime, we are however able to describe completely the asymptotic behavior of this dynamics as long as the initial configuration satisfies some natural constraints. Besides these technical results, we have strong reasons to believe that our techniques relying on defining an energy function from the transition table of the automaton may be extended to the wider class of threshold automata. Due to space constraint, we refer the reader to [16] for the missing proofs.

Details

MFCS Conference 2007 Conference Paper

Small Alliances in Graphs

  • Rodolfo Carvajal
  • Martín Matamala
  • Ivan Rapaport
  • Nicolas Schabanel

Abstract Let G = ( V, E ) be a graph. A nonempty subset S ⊆ V is a (strong defensive) alliance of G if every node in S has at least as many neighbors in S than in V ∖ S. This work is motivated by the following observation: when G is a locally structured graph its nodes typically belong to small alliances. Despite the fact that finding the smallest alliance in a graph is NP-hard, we can at least compute in polynomial time depth G ( v ), the minimum distance one has to move away from an arbitrary node v in order to find an alliance containing v. We define depth ( G ) as the sum of depth G ( v ) taken over v ∈ V. We prove that depth ( G ) can be at most \(\frac{1}{4}(3n^2-2n+3)\) and it can be computed in time O ( n 3 ). Intuitively, the value depth ( G ) should be small for clustered graphs. This is the case for the plane grid, which has a depth of 2 n. We generalize the previous for bridgeless planar regular graphs of degree 3 and 4. The idea that clustered graphs are those having a lot of small alliances leads us to analyze the value of { S contains an alliance}, with S ⊆ V randomly chosen. This probability goes to 1 for planar regular graphs of degree 3 and 4. Finally, we generalize an already known result by proving that if the minimum degree of the graph is logarithmically lower bounded and if S is a large random set (roughly \(|S| > \frac{n}{2})\), then also r p ( G ) →1 as n → ∞.

Details

TCS Journal 2006 Journal Article

Could any graph be turned into a small-world?

  • Philippe Duchon
  • Nicolas Hanusse
  • Emmanuelle Lebhar
  • Nicolas Schabanel

In addition to statistical graph properties (diameter, degree, clustering, etc.), Kleinberg [The small-world phenomenon: an algorithmic perspective, in: Proc. 32nd ACM Symp. on Theory of Computing (STOC), 2000, pp. 163–170] showed that a small-world can also be seen as a graph in which the routing task can be efficiently and easily done in spite of a lack of global knowledge. More precisely, in a lattice network augmented by extra random edges (but not chosen uniformly), a short path of polylogarithmic expected length can be found using a greedy algorithm with a local knowledge of the nodes. We call such a graph a navigable small-world since short paths exist and can be followed with partial knowledge of the network. In this paper, we show that a wide class of graphs can be augmented into navigable small-worlds.

Details DOI

TCS Journal 2006 Journal Article

Fully asynchronous behavior of double-quiescent elementary cellular automata

  • Nazim Fatès
  • Éric Thierry
  • Michel Morvan
  • Nicolas Schabanel

In this paper we propose a probabilistic analysis of the fully asynchronous behavior (i. e. , two cells are never simultaneously updated, as in a continuous time process) of elementary finite cellular automata (i. e. , { 0, 1 } states, radius 1 and unidimensional) for which both states are quiescent (i. e. , ( 0, 0, 0 ) ↦ 0 and ( 1, 1, 1 ) ↦ 1 ). It has been experimentally shown in previous works that introducing asynchronism in the global function of a cellular automata was perturbing its behavior, but as far as we know, only few theoretical work exists on the subject. The cellular automata we consider live on a ring of size n and asynchronism is introduced as follows: at each time step one cell is selected uniformly at random and the transition is made on this cell while the others stay in the same state. Among the 64 cellular automata belonging to the class we consider, we show that 9 of them diverge on all non-trivial configurations while the 55 other converge almost surely to a random fixed point. We show that the exact convergence time of these 55 automata can only take the following values: either 0, Θ ( n ln n ), Θ ( n 2 ), Θ ( n 3 ) or Θ ( n 2 n ). Furthermore, the global behavior of each of these cellular automata is fully determined by reading its code.

Details DOI

TCS Journal 2005 Journal Article

Close to optimal decentralized routing in long-range contact networks

  • Emmanuelle Lebhar
  • Nicolas Schabanel

In order to explain the ability of individuals to find short paths to route messages to an unknown destination, based only on their own local view of a social network (the small world phenomenon), Kleinberg [The small-world phenomenon: an algorithmic perspective, Proc. 32nd ACM Symp. on Theory of Computing, 2000, pp. 163–170] proposed a network model based on a d-dimensional lattice of size n augmented with k long-range directed links per node. Individuals behavior is modeled by a greedy algorithm that, given a source and destination, forwards a message to the neighbor of the current holder, which is the closest to the destination. This algorithm computes paths of expected length Θ ( log 2 n / k ) between any pair of nodes. Other topologies have been proposed later on to improve greedy algorithm performance. But, Aspnes et al. [Fault-tolerant routing in peer-to-peer systems, in: Proc. of ACM 3st Symp. on Princ. of Distr. Comp. (PODC 2002), Vol. 31, 2002, pp. 223–232] shows that for a wide class of long-range link distributions, the expected length of the path computed by this algorithm is always Ω ( log 2 n / ( k 2 log log n ) ). We design and analyze a new decentralized routing algorithm, in which nodes consult their neighbors near by, before deciding to whom forward the message. Our algorithm uses similar amount of computational resources as Kleinberg's greedy algorithm: it is easy to implement, visits O ( log 2 n / log 2 ( 1 + k ) ) nodes on expectation and requires only Θ ( log 2 n / log ( 1 + k ) ) bits of memory—note that [G. S. Manku, M. Naor, U. Wieder, Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks, in: Proc. of 36th ACM STOC 2004, 2004, to appear], shows that any decentralized algorithm visits at least Ω ( log 2 n / k ) on expectation. Our algorithm computes however a path of expected length O ( log n ( log log n ) 2 / log 2 ( 1 + k ) ) between any pair of nodes. Our algorithm might fit better some human social behaviors (such as web browsing) and may also have successful applications to peer-to-peer networks where the length of the path along which the files are downloaded, is a critical parameter of the network performance.

Details DOI

MFCS Conference 2005 Conference Paper

Fully Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata

  • Nazim Fatès
  • Michel Morvan
  • Nicolas Schabanel
  • Eric Thierry

Abstract In this paper we propose a probabilistic analysis of the fully asynchronous behavior (i. e. , two cells are never simultaneously updated, as in a continuous time process) of elementary finite cellular automata (i. e. , {0, 1} states, radius 1 and unidimensional) for which both states are quiescent (i. e. , (0, 0, 0) ↦ 0 and (1, 1, 1) ↦ 1). It has been experimentally shown in previous works that introducing asynchronism in the global function of a cellular automaton may perturb its behavior, but as far as we know, only few theoretical work exist on the subject. The cellular automata we consider live on a ring of size n and asynchronism is introduced as follows: at each time step one cell is selected uniformly at random and the transition rule is applied to this cell while the others remain unchanged. Among the sixty-four cellular automata belonging to the class we consider, we show that fifty-five other converge almost surely to a random fixed point while nine of them diverge on all non-trivial configurations. We show that the convergence time of these fifty-five automata can only take the following values: either 0, Θ( n ln n ), Θ( n 2 ), Θ( n 3 ), or Θ( n 2 n ). Furthermore, the global behavior of each of these cellular automata can be guessed by simply reading its code.

Details
v2026.09.13