Ivan Rapaport

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.

TCS Journal 2013 Journal Article

Discrete mathematical structures: From dynamics to complexity

• Cristian Calude
• Bruno Durand
• Anahí Gajardo
• Dominique Perrin
• Ivan Rapaport
• Sergio Rica

TCS Journal 2013 Journal Article

Letting Alice and Bob choose which problem to solve: Implications to the study of cellular automata

• Raimundo Briceño
• Ivan Rapaport

In previous works we found necessary conditions for a cellular automaton (CA) in order to be intrinsically universal (a CA is said to be intrinsically universal if it can simulate any other). The idea was to introduce different canonical communication problems, all of them parameterized by a CA. The necessary condition was the following: if Ψ is an intrinsically universal CA then the communication complexity of all the canonical problems, when parameterized by Ψ, must be maximal. In this paper, instead of introducing a new canonical problem, we study the setting where they can all be used simultaneously. Roughly speaking, when Alice and Bob –the two parties of the communication complexity model–receive their inputs they may choose online which canonical problem to solve. We give results showing that such freedom makes this new problem, that we call Ovrl, a very strong filter for ruling out CAs from being intrinsically universal. More precisely, there are some CAs having high complexity in all the canonical problems but have much lower complexity in Ovrl.

TCS Journal 2012 Journal Article

Distributed computing of efficient routing schemes in generalized chordal graphs

• Nicolas Nisse
• Ivan Rapaport
• Karol Suchan

Efficient algorithms for computing routing tables should take advantage of particular properties arising in large scale networks. Two of them are of special interest: low (logarithmic) diameter and high clustering coefficient. High clustering coefficient implies the existence of few large induced cycles. Considering this fact, we propose here a routing scheme that computes short routes in the class of k -chordal graphs, i. e. , graphs with no induced cycles of length more than k. In the class of k -chordal graphs, our routing scheme achieves an additive stretch of at most k − 1, i. e. , for all pairs of nodes, the length of the route never exceeds their distance plus k − 1. In order to compute the routing tables of any n -node graph with diameter D we propose a distributed algorithm which uses O ( log n ) -bit messages and takes O ( D ) time. The corresponding routing scheme achieves the stretch of k − 1 on k -chordal graphs. We then propose a routing scheme that achieves a better additive stretch of 1 in chordal graphs (notice that chordal graphs are 3-chordal graphs). In this case, distributed computation of routing tables takes O ( min { Δ D, n } ) time, where Δ is the maximum degree of the graph. Our routing schemes use addresses of size log n bits and local memory of size 2 ( d − 1 ) log n bits per node of degree d.

TCS Journal 2011 Journal Article

Traced communication complexity of cellular automata

• Eric Goles
• Pierre Guillon
• Ivan Rapaport

We study cellular automata with respect to a new communication complexity problem: each of two players know half of some finite word, and must be able to tell whether the state of the central cell will follow a given evolution, by communicating as little as possible between each other. We present some links with classical dynamical concepts, especially equicontinuity, expansivity, entropy and give the asymptotic communication complexity of most elementary cellular automata.

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.

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 → ∞.

TCS Journal 2004 Journal Article

Cellular automata and communication complexity

• Christoph Dürr
• Ivan Rapaport
• Guillaume Theyssier

The model of cellular automata is fascinating because very simple local rules can generate complex global behaviors. The relationship between local and global function is subject of many studies. We tackle this question by using results on communication complexity theory and, as a by-product, we provide (yet another) classification of cellular automata.

TCS Journal 2004 Journal Article

Domino tilings and related models: space of configurations of domains with holes

• Sébastien Desreux
• Martin Matamala
• Ivan Rapaport
• Eric Rémila

We first prove that the set of domino tilings of a fixed finite figure is a distributive lattice, even in the case when the figure has holes. We then give a geometrical interpretation of the order given by this lattice, using (not necessarily local) transformations called flips. This study allows us to formulate an exhaustive generation algorithm and a uniform random sampling algorithm. We finally extend these results to other types of tilings (calisson tilings, tilings with bicolored Wang tiles).

TCS Journal 2003 Journal Article

Tiling with bars under tomographic constraints

• Christoph Dürr
• Eric Goles
• Ivan Rapaport
• Eric Rémila

We wish to tile a rectangle or a torus with only vertical and horizontal bars of a given length, such that the number of bars in every column and row equals given numbers. We present results for particular instances and for a more general problem, while leaving open the initial problem.

SODA Conference 2002 Conference Paper

Tiling groups for Wang tiles

• Cristopher Moore
• Ivan Rapaport
• Eric Rémila

TCS Journal 1999 Journal Article

Tiling allowing rotations only

• Eric Goles
• Ivan Rapaport

We define a “rotating board” as a finite square with one tile fixed in each cell. These fixed tiles can only be rotated and, in addition, they belong to a particular set of four tiles constructed with two colors. In this paper we show that any set of tiles T may be coded in linear time into a “rotating board” B in the following sense: 1. i. There exists an injection from the colors of the tiles of T into the set of border conditions of the board B. 2. ii. There is a one-to-one relation between the set T and the set of tilings of B (obtained by rotating its tiles) satisfying that each t ϵ T is associated to a tiling B θ in such a way that the (north, south, east and west) colors of t are related to the (north, south, east and west) border conditions of B θ by the injection of i. The existence of this coding means that we can efficiently transform an arbitrary degrees of freedom tiling problem (in which to each cell is assigned an arbitrary set of admissible tiles) into a restricted four degrees of freedom problem (in which the tiles, fixed in each cell, can only be rotated). Considering the classical tiling results, we conclude the NP-completeness (resp. undecidability) of the natural bounded (resp. unbounded) version of the rotation tiling problem.

MFCS Conference 1998 Conference Paper

Additive Cellular Automata over Z p and the Bottom of (CA, <=)

• Jacques Mazoyer
• Ivan Rapaport

Abstract In a previous work we began to study the question of “how to compare” cellular automata (CA). In that context it was introduced a preorder (CA, ≤) admitting a global minimum and it was shown that all the CA satisfying very simple dynamical properties as nilpotency or periodicity are located “on the bottom of (CA, ≤)”. Here we prove that also the (algebraically amenable) additive CA over ℤ p are located on the bottom of (CA, ≤). This result encourages our conjecture that says that the “distance” from the minimum could represent a measure of “complexity” on CA. We also prove that the additive CA over ℤ p with p prime are pairwise incomparable. This fact improves our understanding of (CA, ≤) because it means that the minimum, even in the canonical order compatible with ≤, has infinite outdegree.