Homepage
Contact
Campus Peñalolen · Av. Diagonal Las Torres 2640, Peñalolén, Santiago (Chile).
Biography
Current positions.
2022-present Assistant Professor, Faculty of Engineering and Sciences, Universidad Adolfo Ibáñez.
2021-2022 Postdoc at Faculty of Engineering and Sciences, Universidad Adolfo Ibáñez.
Education
2011-2017 Universidad de Chile, Faculty of Physical and Mathematical Sciences, Mathematical Engineering.
2016-2017 Universidad de Chile, Faculty of Physical and Mathematical Sciences, Master in Engineering Sciences with specialization in Applied Mathematics.
2018-2021 Universidad de Chile, Faculty of Physical and Mathematical Sciences, PhD in Engineering Sciences, with specialization in Mathematical Modeling.
2018-2021 Aix-Marseille Université, École Doctorale en Mathématiques et Informatique de Marseille (ED184) , LIS – Laboratoire d’Informatique et Systèmes – UMR 7020, Doctorat en Informatique. International joint PhD thesis.
PhD. thesis
On automata networks dynamics: an approach based on computational complexity theory.
Alejandro Maass - Eric Goles (Chile) / Sylvain Sené - Guillaume Theyssier (France)
Abstract
An automata network (AN) is a network of entities, each holding a state from a finite set and related by a graph structure called an interaction graph. Each node evolves according to the states of its neighbors in the interaction graph, defining a discrete dynamical system. This thesis work explores two main questions: a) what is the link between dynamical and computational properties of an AN? and b) what is the impact of the interaction graph topology on the global dynamics of an AN?. In order to tackle the first question a notion of computational complexity of an AN family is defined in terms of the computational complexity of decision problems related to the dynamics of the network. On the other hand, the dynamical complexity of a particular AN family is defined in terms of the existence of attractors of exponential period. A strong link between these two last definitions is presented in terms of the notion of simulation between AN families. In this context, complexity is characterized from a localized standpoint by studying the existence of structures called coherent gadgets which satisfy two properties: i) they can locally interact in a coherent way as dynamical systems and ii) they are capable of simulating a finite set of functions defined over a fixed finite set. Finally, the second question is addressed in the context of a well-known family called freezing automata networks. An AN is freezing if there is an order on states such that the state evolution of any node is non-decreasing in any orbit. A general model checking problem capturing many classical decision problems is presented. In addition, when three graph parameters, the maximum degree, the treewidth and the alphabet size are bounded, a fast-parallel algorithm that solves general model checking problem is presented. Moreover, it is shown that the latter problem is unlikely to be fixed-parameter tractable on the treewidth parameter as well as on the alphabet size when considered as single parameters.
Keywords: discrete math - dynamical systems - computational complexity - complex systems - automata networks - systems biology.
Publications
Articles in Journals
2024 Intrinsic Universality in Automata Networks II: Gluing and Gadgets, Martín Ríos-Wilson and Guillaume Theyssier, Theoretical Computer Science, 2024, p. 114779.[Online version] [Preprint]
2024 Intrinsic Universality in Automata Networks I: Families and Simulations, Martín Ríos-Wilson and Guillaume Theyssier, Theoretical Computer Science, 2024, vol. 997, p. 114511.[Online version] [Preprint]
2024 On the parameterized complexity of freezing dynamics, Eric Goles, Pedro Montealegre, Martín Ríos-Wilson, Guillaume Theyssier, Advances in Applied Mathematics, 157, 102706 [Online version][Preprint]
2023 Distributed maximal independent set computation driven by finite-state dynamics. Goles, E., Leal, L., Montealegre, P., Rapaport, I., & Ríos-Wilson, M. International Journal of Parallel, Emergent and Distributed Systems, 38(1), 85-97. [Online version]
2023 Exploring the Dynamics of Fungal Cellular Automata, Carlos S. Sepúlveda, Eric Goles, Martín Ríos-Wilson, Andrew Adamatzky. International Journal of Unconventional Computing [Online version][Preprint]
2022 Introducing the activity parameter for elementary cellular automata, Pablo Concha-Vega, Eric Goles, Pedro Montealegre, Martín Ríos-Wilson, Julio Santivañez, International Journal of Modern Physics C, 2250121, 2022.
2022 On the complexity of generalized Q2R automaton, Eric Goles, Pedro Monteale- gre, Marco Montalva-Medel, Martín Ríos-Wilson, Advances in Applied Mathematics 138, 102355, Academic Press, 2022/7/1.
2021 On the Complexity of Asynchronous Freezing Cellular Automata, Eric Goles, Diego Maldonado, Pedro Montealegre, Martín Ríos-Wilson, Information and Computation, Information and Computation, 2021, 104764, ISSN 0890-5401. In Press. [Online version] [Preprint]
2021 Generating Boolean functions on totalistic automata networks, Andrew Adamatzky, Eric Goles, Pedro Montealegre, Martín Ríos-Wilson, Int. J. Unconv. Comput. 16(4): 343-391 [Online version] [Preprint]
2020 On the effects of firing memory in the dynamics of conjunctive networks, Eric Goles, Pedro Montealegre, Martín Ríos-Wilson, Discrete and Continuous Dynamical Systems - A, 40(10): 5765-5793. [Online version] [Preprint]
Articles in Conference Proceedings
2024 The Hardness of Local Certification of Finite-State Dynamics, Diego Maldonado, Pedro Montealegre, Martín Ríos-Wilson. In: LATIN 2024. [Proceedings version] [Preprint]
2024 On Elementary Cellular Automata Asymptotic (A)synchronism Sensitivity and Complexity, Isabel Donoso-Leiva, Eric Goles, Martín Ríos-Wilson, Sylvain Sené. In: LATIN 2024. [Proceedings version][Preprint]
2024 Local Certification of Majority Dynamics. Maldonado, D., Montealegre, P., Ríos-Wilson, M., Theyssier, G. In: Fernau, H., Gaspers, S., Klasing, R. (eds) SOFSEM 2024: Theory and Practice of Computer Science. SOFSEM 2024. Lecture Notes in Computer Science, vol 14519. Springer, Cham. [Proceedings version][Preprint]
2022 Computing Power of Hybrid Models in Synchronous Networks., Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Iván Rapaport, Martín Ríos-Wilson, Ioan Todinca, In: Conference On Principles Of Distributed Systems (OPODIS 2022). [Proceedings version] [Preprint]
2022 Brief Announcement: Computing Power of Hybrid Models in Synchronous Networks., Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Iván Rapaport, Martín Ríos-Wilson, Ioan Todinca, In: 36th International Symposium on Distributed Computing (DISC 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik. [Proceedings version] [Preprint]
2021 On the impact of treewidth in the computational complexity of freezing dynamics, Eric Goles, Pedro Montealegre, Martín Ríos-Wilson, Guillaume Theyssier, In: De Mol L., Weiermann A., Manea F., Fernández-Duque D. (eds) Connecting with Computability. CiE 2021. Lecture Notes in Computer Science, vol 12813. Springer, Cham. [Proceedings version] [Preprint]
2019 On the effects of firing memory in the dynamics of conjunctive networks, Eric Goles, Pedro Montealegre, Martín-Ríos Wilson, In: Castillo-Ramirez A., de Oliveira P. (eds) Cellular Automata and Discrete Complex Systems. AUTOMATA 2019. Lecture Notes in Computer Science, vol 11525. Springer, Cham. [Proceedings version] [Preprint]
Book chapters
2023 Exploring Dynamics of Fungal Cellular Automata. Sepúlveda, C.S., Goles, E., Ríos-Wilson, M., Adamatzky, A. (2023). In: Adamatzky, A. (eds) Fungal Machines. Emergence, Complexity and Computation, vol 47. Springer, Cham. [Online version]
2021 Computing the Probability of Getting Infected: On the Counting Complexity of Bootstrap Percolation, Pedro Montealegre and Martín Ríos-Wilson, In: Automata and Complexity. Essays presented to Eric Goles on the occasion of his 70th birthday, Emergence, Complexity and Computation, Springer. [Online version]
Supervised Students
PhD.
PhD.
2023-today. Isabel Donoso Leiva.
International joint PhD. thesis: PhD. program in Complex System Engineering, Universidad Adolfo Ibáñez and Doctorat en Informatique, École Doctorale en Mathématiques et Informatique de Marseille ED184, Aix-Marseille Université. co-supervised with Eric Goles (Universidad Adolfo Ibáñez) and Sylvain Sené (LIS, Aix-Marseille Université).
2024-today Gerardo Dos Ramos,
PhD program in Data Science, Universidad Adolfo Ibáñez, co-supervised with Pedro Montealegre (Universidad Adolfo Ibáñez)
Master
Master.
2024-today Vicente Carrión,
Master of Science in Data Science, Universidad Adolfo Ibáñez
Services
Current
I am the organizer of the sessions for the DISC (PhD Program in Complex Systems Engineering, Universidad Adolfo Ibáñez) seminar.
Past
Oranizing First Workshop on Complex Systems Chile-France (2024)
Organizing XVIII Escuela de Verano en Matemáticas Discretas (2023)
Organizing the Workshop The Automata Factory 4
Organizing the Workshop Escuela Predoctoral DISC 2021
Organizing Committee of the workshop The Automata Factory 3 3 (2020)
Grants and Awards
2023-2024 STIC-AmSud. Consensus Cellular Automata Algorithms and Tie-Majority Classification (CAMA) cod - 22-STIC-02
2022-2025 ANID, Postdoctorado 2022, From local to global behavior in automata networks: a computational complexity approach.
2019-2020 Programme Claude Gay Chili-France, Embassy of France in Chile and French Institute, Fellowship granted in the context of an international joint PhD supervision agreement.
2017-2021 CONICYT, Formation of Advance Human Capital, Competitive call for doctorate scholarships in Chile 2018.