PCPablo Concha-Vega

Pablo Concha-Vega

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

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Pablo Concha-Vega has a total of 3 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • 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.