KPKévin Perrot

Kévin Perrot

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Kévin Perrot has a total of 26 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Hardness of monadic second-order formulae over succinct graphs

    by Guilhem Gamard, Aliénor Goubault-Larrecq, Pierre Guillon, Pierre Ohlmann, Kévin Perrot, Guillaume Theyssier

    Our main result is a succinct counterpoint to Courcelle's meta-theorem as follows: every cw-nontrivial monadic second-order (MSO) property is either NP-hard or coNP-hard over graphs given by succinct representations. Succint representations are Boolean circuits computing the adjacency relation. Cw-nontrivial properties are those which have infinitely many models and infinitely many countermodels with bounded cliquewidth. Moreover, we explore what happens when the cw-nontriviality condition is dropped and show that, under a reasonable complexity assumption, the previous dichotomy fails, even for questions expressible in first-order logic.


  • Timed Prediction Problem for Sandpile Models

    by Pablo Concha-Vega, Kévin Perrot

    • 22 September 2025
    • Published by HAL in HAL
    Open Access

    Complexity of the Freezing Majority Rule with L-shaped Neighborhoods

    by Pablo Concha-Vega, Eric Goles, Pedro Montealegre, Kévin Perrot

    In this article we investigate the computational complexity of predicting two dimensional freezing majority cellular automata with states {-1, +1}, where the local interactions are based on an L-shaped neighborhood structure. In these automata, once a cell reaches state +1, it remains fixed in that state forever, while cells in state -1 update to the most represented state among their neighborhoods. We consider L-shaped neighborhoods, which mean that the vicinity of a given cell c consists in a subset of cells in the north and east of c.We focus on the prediction problem, a decision problem that involves determining the state of a given cell after a given number of time-steps. We prove that when restricted to the simplest L-shaped neighborhood, consisting of the central cell and its nearest north and east neighbors, the prediction problem belongs to NC, meaning it can be solved efficiently in parallel. We generalize this result for any L-shaped neighborhood of size two. On the other hand, for other L-shaped neighborhoods, the problem becomes P-complete, indicating that the problem might be inherently sequential.

  • Open Access

    Complexity of the Freezing Majority Rule with L-shaped Neighborhoods

    by Pablo Concha-Vega, Eric Goles, Pedro Montealegre, Kévin Perrot

    In this article we investigate the computational complexity of predicting two dimensional freezing majority cellular automata with states $\{-1,+1\}$, where the local interactions are based on an L-shaped neighborhood structure. In these automata, once a cell reaches state $+1$, it remains fixed in that state forever, while cells in state $-1$ update to the most represented state among their neighborhoods. We consider L-shaped neighborhoods, which mean that the vicinity of a given cell $c$ consists in a subset of cells in the north and east of $c$. We focus on the prediction problem, a decision problem that involves determining the state of a given cell after a given number of time-steps. We prove that when restricted to the simplest L-shaped neighborhood, consisting of the central cell and its nearest north and east neighbors, the prediction problem belongs to $\mathsf{NC}$, meaning it can be solved efficiently in parallel. We generalize this result for any L-shaped neighborhood of size two. On the other hand, for other L-shaped neighborhoods, the problem becomes $\mathsf{P}$-complete, indicating that the problem might be inherently sequential.

  • Open Access

    Timed Prediction Problem for Sandpile Models

    by Pablo Concha-Vega, Kévin Perrot

    We investigate the computational complexity of the timed prediction problem in two-dimensional sandpile models. This question refines the classical prediction problem, which asks whether a cell q will eventually become unstable after adding a grain at cell p from a given configuration. The prediction problem has been shown to be P-complete in several settings, including for subsets of the Moore neighborhood, but its complexity for the von Neumann neighborhood remains open. In a previous work, we provided a complete characterization of crossover gates (a key to the implementation of non-planar monotone circuits) for these small neighborhoods, leading to P-completeness proofs with only 4 and 5 neighbors among the eight adjancent cells. In this paper, we introduce the timed setting, where the goal is to determine whether cell q becomes unstable exactly at time t. We distinguish several cases: some neighborhoods support complete timed toolkits (including timed crossover gates) and exhibit P-completeness; others admit timed crossovers but suffer from synchronization issues; planar neighborhoods provably do not admit any timed crossover; and finally, for some remaining neighborhoods, we conjecture that no timed crossover is possible.

    • 25 June 2025
    • Published by HAL in HAL
    Open Access

    Timed Prediction Problem for Sandpile Models

    by Pablo Concha-Vega, Kévin Perrot

    We investigate the computational complexity of the timed prediction problem in two-dimensional sandpile models. This question refines the classical prediction problem, which asks whether a cell q will eventually become unstable after adding a grain at cell p from a given configuration. The prediction problem has been shown to be P-complete in several settings, including for subsets of the Moore neighborhood, but its complexity for the von Neumann neighborhood remains open. In a previous work, we provided a complete characterization of crossover gates (a key to the implementation of non-planar monotone circuits) for these small neighborhoods, leading to P-completeness proofs with only 4 and 5 neighbors among the eight adjancent cells. In this paper, we introduce the timed setting, where the goal is to determine whether cell q becomes unstable exactly at time t. We distinguish several cases: some neighborhoods support complete timed toolkits (including timed crossover gates) and exhibit P-completeness; others admit timed crossovers but suffer from synchronization issues; planar neighborhoods provably do not admit any timed crossover; and finally, for some remaining neighborhoods, we conjecture that no timed crossover is possible.

  • Sandpiles prediction and crossover on $\mathbb {Z}^2$ within Moore neighborhood

    by Pablo Concha-Vega, Eric Goles, Pedro Montealegre, Kévin Perrot


  • Open Access

    Interaction graphs of isomorphic automata networks I: complete digraph and minimum in-degree

    by Florian Bridoux, Kévin Perrot, Aymeric Picard Marchetto, Adrien Richard

    An automata network with $n$ components over a finite alphabet $Q$ of size $q$ is a discrete dynamical system described by the successive iterations of a function $f:Q^n\to Q^n$. In most applications, the main parameter is the interaction graph of $f$: the digraph with vertex set $[n]$ that contains an arc from $j$ to $i$ if $f_i$ depends on input $j$. What can be said on the set $\mathbb{G}(f)$ of the interaction graphs of the automata networks isomorphic to $f$? It seems that this simple question has never been studied. Here, we report some basic facts. First, we prove that if $n\geq 5$ or $q\geq 3$ and $f$ is neither the identity nor constant, then $\mathbb{G}(f)$ always contains the complete digraph $K_n$, with $n^2$ arcs. Then, we prove that $\mathbb{G}(f)$ always contains a digraph whose minimum in-degree is bounded as a function of $q$. Hence, if $n$ is large with respect to $q$, then $\mathbb{G}(f)$ cannot only contain $K_n$. However, we prove that $\mathbb{G}(f)$ can contain only dense digraphs, with at least $\lfloor n^2/4 \rfloor$ arcs.