Welcome to the webpage of the CANA team
from Laboratoire d’Informatique et Systèmes (UMR CNRS 7020).


Natural Computation research group

Description

Natural computation is a field of computer science. It is based on the links between informatics and other disciplines, mainly physics and biology. On the one hand, it aims at abstracting natural phenomena in order to develop new computational paradigms, or deepening the study of well-known nature-inspired models of computation. On the other hand, it aims at using these models of computation in order to achieve a better understanding of the phenomena at hand, with the hope to unravel some of the underlying fundamental laws.

The CANA research group (CANA is for ‘‘CAlcul NAturel’’, a French acronym for natural computation), in particular, seeks to capture at the formal level some of the fundamental paradigms of theoretical biology and physics, via the models and approaches of theoretical computer science and discrete mathematics. These approaches and their underlying methods, that we develop also per se, rest on the study of interacting entities. Most often in the models that we study, each of the constitutive entities is elementary and can only take a finite number of states. Moreover, they interact only locally with respect to the network on which they lie in discrete time steps. In spite of their apparent simplicity, these discrete models are able to capture the essence of the dynamics of numerous natural systems, upon which they shed a new light. For instance, thanks to their high level of abstraction, these models provide a qualitative representation of biological regulation networks, of particle propagation in quantum physics, or even of the emergence of waves in sandpiles. Beyond their ability to grasp natural phenomena, the models are also being studied for their own sake, in terms of their intrinsic dynamical, computability and complexity properties.

To define nature-inspired discrete models; to demonstrate their relevance; to tame the complex behaviours that they generate by means of rigorous mathematical results; to use this to better understand real systems: these are the main concerns of CANA research team.

Depending on the situation, the important features of the model can be of static (syntactic) or dynamical (semantic) nature. Moreover, the network of entities may be regular or not, the interaction rules may be deterministic, probabilistic, synchronous or asynchronous… We study these models and their variations both for their representational and computational abilities.

The methods used come from discrete dynamical system theory, combinatorics, complexity and computability theories, and non-monotonic logic, linear algebra, quantum computing and quantum information.

Keywords

(Non-)deterministic, probabilistic or quantum discrete dynamical systems;
Interaction networks: automata networks, quantum and classical cellular automata, quantum walks, sandpiles;
Inspirations from and applications to molecular biology, medicine and physics.


Members

Permanent team members

Non-permanent team members

PhD students

Associate team members

  • Adrien Richard, chargé de recherches CNRS, I3S, Nice Sophia Antipolis, France.

Past members

Past permanent members

  • 2014-2020 – Pablo Arrighi, professeur des universités, now member of the LMF (Saclay).

Past PhD students

  • 2021-2024 (36 months) – Pablo Concha, PhD with Kévin, Eric Goles and Pedro Montealegre (Chilean funding, 2021-2024). Currently ATER at AMU, LIS (CANA).
  • 2018-2022 (50 months) – Amélia Durbec, PhD with Pablo (MESR/ED184 funding, 2018-2021). Currently on a postdoc position at LUNIQ team, JUNIA (engineering school), Lille.
  • 2019-2022 (36 months) – Kevissen Sellapillay, PhD with Giuseppe and Alberto Verga (MESR/ED352 funding, 2019-2022). Currently on a postdoc position at the Forschungszentrum Jülich
  • 2019-2022 (36 months) – Balthazar Casalé, PhD with Giuseppe and Hachem Kadri (ANR funding, 2019-2022). Currently unknown position.
  • 2019-2022 (36 months) – Nathanaël Eon, PhD with Giuseppe and Pablo (MESR/ED184 funding, 2019-2022). Currently on a humanitarian mission.
  • 2018-2021 (38 months) – Martín Ríos Wilson, PhD with Sylvain and Guillaume Theyssier on the French side, and Alejandro Maass and Eric Goles on the Chilean side (Chilean funding, 2018-2021). Currently Assistant professor at the University Adolfo Ibañez, Santiago, Chile.
  • 2016-2021 (50 months) – Cédric Bérenger, PhD with Kévin and Peter Niebert (MESR/ED184 funding, 2016-2021). Currently R&D engineer in embedded systems at CB-Embedded, Marseille.
  • 2017-2021 (40 months) – Pacôme Perrotin, PhD with Kévin and Sylvain (MESR/ED184 funding, 2017-2021). Currently on a postdoc position at the Mackenzie University, Sao Paulo, Brazil.
  • 2016-2019 (38 months) – Ivan Márquez Martín, PhD with Giuseppe and Pablo (Spanish funding, 2016-2019). Currently cybersecurity consultant at Evolutio Empowering the Cloud, Madrid.
  • 2016-2019 (32 months) – Florian Bridoux, PhD with Sylvain, Guillaume Theyssier and Adrien Richard (MESR/Labex Archimède funding, 2016-2019). Currently maître de conférences at I3S at University Côte d’Azur, Nice.
  • 2015-2018 (38 months) – Jose Luis Vilchis Medina, PhD with Pierre and Andrei Doncescu (Mexican funding, 2015-2018). Currently maître de conférences at the École navale, Brest.

Past other non-permanent team members

  • 2023-2024 (12 months) – Ilya Galanov, ATER.
  • 2022-2023 (6 months) – Alexis Toumi, postdoc with Giuseppe and Pierre Clairambault (PEPR EPiQ). Currently research and development scientist at PlantingSpace and scientific advisor at Quantinuum.
  • 2021-2022 (12 months) – Victor Lutfalla, ATER. Currently on a postdoc position at I2M at Aix-Marseille University.
  • 2020-2022 (24 months) – Pacôme Perrotin, ATER. Currently on a postdoc position at the Mackenzie University, Sao Paulo, Brazil.
  • 2020-2021 (12 months) – Étienne Moutot, postdoc with Giuseppe and Pablo (John Templeton QISS project funding). Currently chargé de recherche CNRS at I2M at Aix-Marseille University.
  • 2019-2021 (22 months) – Guilhem Gamard, postdoc with Sylvain (ANR FANs funding). Currently maître de conférences at LORIA at the University of Lorraine, Nancy.
  • 2019-2021 (24 months) – Florian Bridoux, ATER. Currently maître de conférences at I3S, University Côte d’Azur, Nice.
  • 2018-2019 (12 months) – Jose Luis Vilchis Medina, ATER. Currently maître de conférences at the École navale, Brest.
  • 2016-2017 (12 months) – Timo Jolivet, postdoc with Sylvain (Labex Archimède funding). Currently full-time musician, Marseille.
  • 2015-2018 (36 months) – Stefano Facchini, postdoc with Pablo (12 months, Labex Archimède funding) then ATER (24 months). Currently unknown position.
  • 2013-2014 (6 months) – Pierre-Étienne Meunier, postdoc with Sylvain (LIF funding). Currently CSO of Albedo Énergie, Cofounder of coturnix.fr, Chief Conflict Resolver at pijul.org.

Past graduate students

2022-2023

  • Marius Rolland, M2 Computer science and discrete mathematics AMU, on primality in finite dynamical systems, with Enrico and Kévin (5 months).
  • Denis Belle, M1 Computer science and discrete mathematics AMU, on firing squad synchronization problem, with Kévin (2 months).
  • Thibault Schneeberger, M1 Computer science and discrete mathematics AMU, on learnability, with Kévin, Cécile Capponi and Hachem Kadri (2 months).

2021-2022

  • Mathieu Roget, 4th year of Computer science ENS Lyon (long research project), on rigourous study of a faut tolerant quantum search, with Giuseppe (3 months).
  • Anirban Ganguly, M2 Theoretical Physics AMU, on random Clifford quantum circuits and information recovery in black holes, with Giuseppe and Federico Piazza (CPT) (5 months).
  • Nicolas Jolly, 2th year of Theoretical Physics ENS Paris, on twisted quantum walks, with Giuseppe (3 months).
  • Marc Chouraqui, M1 Computer science and discrete mathematics AMU, on the universality of ECA rule 54, with Kévin (2 months).
  • Alienor Goubault-Larrecq, M2 Computer science ENS Lyon, on P-complete FO properties of automata networks, with Antonio and Kévin (5 months).
  • Marius Rolland, M1 Computer science and discrete mathematics AMU, on unconventional crossings in 2D sandpiles, with Kévin (2 months).
  • Léah Tapin, M2 Computer science and discrete mathematics AMU, on complex update schedules in automata networks, with Kévin and Sylvain (5 months).

2020-2021

  • Lucas Venturini, 4th year of Computer science ENS Lyon (long research project), on deterministic periodic update of Boolean automata networks, with Kévin and Sylvain (5 months).
  • Johan Couturier, M2 Computer science and discrete mathematics AMU, on algebraic decomposition of finite dynamical systems, with Antonio (4 months).
  • Mathieu Roget, M2 Computer science ENS Lyon, on new statistical trade-off for quantum perceptron, with Giuseppe and Hachem Kadri (5 months).
  • Thomas Usimaki, M2 Computer science and discrete mathematics AMU, on building graphs states in optimal time, with Giuseppe and Alan Gardin (4 months).
  • Julien Zylberman, M2 Physics ENS Paris, on relativistic fluido-dynamics on quantum computer, with Giuseppe and Nuno Loureiro (5 months)

2019-2020

  • Odilon Duranthon, M2 Physics ENS Paris, on coarse-graining maps over quantum cellular automata, with Giuseppe (5 months).
  • Caroline Gaze-Maillot, M2 Computer science and discrete mathematics AMU, on semiring of dynamical systems, with Antonio (4 months).
  • Basile Herzog, M2 Physics Sorbonne, on non-linear quantum walks applied to quantum algorithmics, with Giuseppe (4 months).
  • Leo Kammerlocher, M2 Computer science and discrete mathematics AMU, on randomisation in symplectic and non reversible cellular automata, with Giuseppe, Nathanaël and Guillaume Theyssier (5 months).
  • Sokratis Varelogiannis, M2 Polytechnique, on Quantum walks for the Grover search, with Giuseppe and Pablo (3 months).
  • Marin Costes, M1 Computer science ENS Paris-Saclay, on Gauge-invariant CA, with Giuseppe, Nathanaël and Pablo (3 months).
  • Smith-Etchanm Djamoura, M1 Polytech Sophia, on predicting 1D sandpiles, with Kévin and Enrico Formenti (2 months).

2018-2019

  • Balthazar Casalé M2 Computer science AMU, on quantum bandit problem, with Giuseppe and Hachem Kadri (5 months).
  • Nathanaël Eon, M2 ECM, on non-Abelian gauge invariant cellular automata, with Giuseppe and Pablo (5 months).
  • Alan Gardin, M2 IMT Atlantique, on two-interacting-quantum walkers, with Giuseppe (4 months).
  • Karmouda Ouafae, M2 Computer science AMU, on learning algorithms for separability and entanglement detection, with Giuseppe and Hachem Kadri (5 months).
  • Kevissen Sellapillay, M2 Physics ENS Paris, on general covariant quantum walks, with Giuseppe, Ivan, and Pablo (5 months).
  • Julien Aguero, M1 Physics AMU, on two-interacting-quantum walkers, with Giuseppe and Ivan (2 months).
  • Maxime Gabiot, M1 Computer science AMU, on gravity-like cellular automata, with Giuseppe and Antonio (2 months).
  • Caroline Gaze, M1 Computer science AMU, on limit cycle complexity problems in Boolean automata networks, with Kévin and Sylvain (2 months).
  • Stephane Guilliet, M1 Physics AMU, on natural occurring research algorithm, with Giuseppe and Pablo (2 months).
  • Mathieu Vallet, M1 Computer science AMU, on Kinkdomino game, with Kévin (2 months).
  • Lucas Venturini, M1 Computer science ENS Lyon, on update schedules, with Kévin and Sylvain (3 months).

2017-2018

  • Nicolas Durbec, M2 Computer science AMU, on causal graph dynamics, with Pablo (6 months).

2016-2017

  • Talia Lacombe, M2 Computer science AMU, on parallel symmetric sandpiles, with Kévin and Sylvain (6 months).
  • Pacôme Perrotin, M2 Computer science AMU, on compositionnality of Boolean automata networks, with Kévin and Sylvain (6 months).
  • Nicolas Durbec, M1 Computer science AMU, on fixed point complexity problems in Boolean automata networks, with Kévin (2 months).
  • Noé Goudian, M1 Computer science AMU, on causal graph dynamics, with Pablo (2 months).
  • Hà Nguyen, M1 Computer science ENS Lyon, on sandpile crossings, with Kévin (3 months).
  • Abderrahim Radoua, M1 Computer science AMU, on Secure Exchange Protocol, with Kévin and Pablo (3 months).

2015-2016

  • Florian Bridoux, M2 Info Univ. Orléans, on intrinsic simulations of Boolean automata networks, with Kévin, Sylvain, and Pierre Guillon (6 months).

2014-2015

  • Aurore Alcolei, M2 Computer science ENS Lyon, on non-monotone asynchronous Boolean automata networks, with Kévin and Sylvain (6 months).
  • Bastien Rulat, M2 Computer science AMU, on chip firing game dynamics, with Kévin and Sylvain (4 months).
  • Michaël Dubuis, M1 Computer science AMU, on Secure Exchange Protocol, with Kévin and Pablo (2 months).
  • Julien Prudhomme, M1 Computer science AMU, on Secure Exchange Protocol, with Kévin and Pablo (2 months).

2013-2014

  • Michaël Blanc, M2 Computer science AMU, on exponential paths of non-monotone Boolean automata networks, with Pierre-Étienne and Sylvain (6 months).


Projects

  • 2024-2027 (48 months): Automata networks workpackage lead partnership, and AMU local coordination, in EU MSCA-SE project HORIZON-MSCA-2023-SE-01-101131549 project ACANCOS with Brazil, Chile, Finland, and Italy. Application-driven Challenges for Automata Networks and Complex Systems
  • 2023-2024 (24 months): Partnership in STIC AmSud project 22-STIC-02 CAMA with Brazil and Chile. Consensus Cellular Automata Algorithms and Tie-Majority Classification
  • 2022-2028 (72 months) : Local coordination of ANR AMI CMA QuanTEdu-France Technologies quantiques : Éducation et formation pour répondre aux besoins en compétences stratégiques de la recherche et de l’industrie en France
  • 2022-2025 (36 months) : Coordination of ‘Amidex-volet interdisciplinaire’ DisQC Distributed Quantum Computing : Algorithms, Quantum Error Correcting Codes and Implementations
  • 2022-2026 (48 months) : Coordination of JCJC ANR project ANR-22-CE47-0002 DisQC. Distributed Quantum Computing: Algorithms and Implementations
  • 2022-2028 (72 months) : Local coordination of ANR France 2030 PEPR project ANR-22-PETQ-0007 EPiQ Etude de la pile quantique : algorithmes, modèles de calcul et simulation pour l’informatique quantique
  • 2021 (12 months) : Coordination of INS2I project with I2M Fault Invariant Distributed Quantum Algorithms
  • 2020-2022 (36 months) : Partnership in ECOS-Sud project C19E02 SyDySys with Chile. Symbolic dynamical systems: a dialog between finite and infinite
  • 2019-2023 (48+6 months): Coordination of JCJC ANR project ANR-18-CE40-0002 FANs. Foundations of Automata Networks
  • 2019-2022 (48 months): Partnership in John Templeton Foundation Large Grant #61466 QISS. The Quantum Information Structure of Spacetime
  • 2019-2021 (36 months): Partnership in ANR project ANR-19-CE23-0011 QuantML. Quantum Machine Learning: Foundations and Algorithms
  • 2019-2020 (24 months): French coordination of STIC AmSud project 19-STIC-03 (Campus France 43478PD) CoDANet with Brazil and Chile.
    Computation and Dynamics of Deterministic Automata Networks
  • 2019-2020 (18 months): Coordination of Amidex (pépinière d’excellence 2018) project DQTS. Discrete Time Quantum Simulator
  • 2018-2020 (36 months): Coordination of CNRS PICS project GQS with Spain.
    Geometry and Quantum Simulation
  • 2018-2020 (24 months): Partnership in ECOS-Sud project A17C03 QuCA
    with Argentina. Quantum Calculi
  • 2018 (12 months): Coordination of CNRS INFINITI 2018 project LQST.
    Lattice Quantum Simulation Theory
  • 2017-2025 (108 months): Partnership in ANR convergences project
    ANR-16-CONV-00001 CENTURI. Turing centre for living systems
  • 2017-2019 (36 months): French coordination of ECOS-Sud project
    C16E01 ANipad with Chile. Automata Networks: Inverse Problem and Dynamics
  • 2017-2018 (24 months): Coordination of IXXI project SSE
    Sharing the ‘‘sharing economy’’
  • 2017 (12 months): Coordination of CNRS PEPS JCJC INS2I project CGETA
    Graph Compression with Efficient Algorithmic Complexity
  • 2017 (12 months): Coordination of CNRS PEPS JCJC INS2I project QNG
    Quantum Networks and Growing
  • 2017 (6 months): Coordination of AMU Labex Archimède software development project SXP. Secure eXchange Protocol
  • 2016-2018 (24 months): Partnership in Stic-AmSud project 16-STIC-05 FoQCoSS with Argentina. Foundations of Quantum Computation: Syntax and Semantics
  • 2015-2018 (36 months): Coordination of PACA project FRI-2015_01134.
    Interaction Network foundations
  • 2012-2016 (48 months): Partnership in ANR project ANR-12-BS02-0007 TARMAC. Theory of AlgoRithms: Machines, completeness, Axiomatization and physical Constraints


Publications

2024

  1. Concha-Vega, Pablo, Eric Goles, Pedro Montealegre, and Kévin Perrot. “Sandpiles Prediction and Crossover on Z2 within Moore Neighborhood.” Natural Computing, 2024. DOI-link   PDF-link
  2. Nzongani, Ugo, Nathanaël Eon, Márquez-Martı́n Iván, Armando Pérez, Giuseppe Di Molfetta, and Pablo Arrighi. “Dirac Quantum Walk on Tetrahedra.” Physical Review A 110, no. 4 (October 2024): 042418. DOI-link  
  3. Ruivo, Eurico, Kévin Perrot, Pedro Paulo Balbi, and Pacôme Perrotin. “Negative Results on Density Determination with One-Dimensional Cellular Automata with Block-Sequential Asynchronous Updates.” Journal of Computational Science 82 (2024): 102430. DOI-link   HAL-link  
  4. Doré, François, Kévin Perrot, Antonio E. Porreca, Sara Riva, and Marius Rolland. “Roots in the Semiring of Finite Deterministic Dynamical Systems.” In Proceedings of AUTOMATA 2024, 120–32. Springer, 2024. DOI-link   arXiv-link  
  5. Defrain, Oscar, Antonio E. Porreca, and Ekaterina Timofeeva. “Polynomial-Delay Generation of Functional Digraphs up to Isomorphism.” Discrete Applied Mathematics 357 (2024): 24–33. DOI-link   arXiv-link  
  6. Perrot, Kévin, Sylvain Sené, and Léah Tapin. “Complexity of Boolean Automata Networks under Block-Parallel Update Modes.” In Proceedings of SAND’24, 292:19:1–19:19. LIPIcs. Schloss Dagstuhl Publishing, 2024. DOI-link   arXiv-link  
  7. Doré, François, Enrico Formenti, Antonio E. Porreca, and Sara Riva. “Decomposition and Factorisation of Transients in Functional Graphs.” Theoretical Computer Science 999 (June 2024): 114514. DOI-link   arXiv-link  
  8. Roget, Mathieu, and Giuseppe Di Molfeta. “A Quantum Walk-Based Scheme for Distributed Searching on Arbitrary Graphs.” In Proceedings of ASCAT’24, 2021:72–83. Communications in Computer and Information Science. Springer, 2024. DOI-link  
  9. Donoso Leiva, Isabel, Eric Goles, Martín Ríos-Wilson, and Sylvain Sené. “Asymptotic (a)Synchronism Sensitivity and Complexity of Elementary Cellular Automata.” In Proceedings of LATIN’24, 14579:272–86. LNCS. Springer, 2024. DOI-link   arXiv-link  
  10. Perrot, Kévin, Sylvain Sené, and Léah Tapin. “Combinatorics of Block-Parallel Automata Networks.” In Proceedings of SOFSEM’24, 14519:442–55. LNCS. Springer, 2024. DOI-link   arXiv-link  

2023

  1. Bridoux, Florian, Kévin Perrot, Aymeric Picard Marchetto, and Adrien Richard. “Interaction Graphs of Isomorphic Automata Networks I: Complete Digraph and Minimum in-Degree.” Journal of Computer and System Sciences 138 (December 2023): 103458. DOI-link   arXiv-link  
  2. Eon, Nathanaël, Giuseppe Di Molfetta, Giuseppe Magnifico, and Pablo Arrighi. “A Relativistic Discrete Spacetime Formulation of 3+1 QED.” Quantum 7 (November 2023): 1179. DOI-link  
  3. Perrot, Kévin. “Tout Est Complexe.” Interstices – Revue De Culture Scientifique En Ligne Publiée Par Inria, November 2023. Link.  
  4. Formenti, Enrico, Sylvain Sené, and Guillaume Theyssier, eds. Current Trends in Cellular Automata and Automata Networks. Vol. 22. Natural Computing. Springer, 2023. DOI-link   PDF-link
  5. Aracena, Julio, Florian Bridoux, Pierre Guillon, Kevin Perrot, Adrien Richard, and Guillaume Theyssier. “On the Dynamics of Bounded-Degree Automata Networks.” In Proceedings of AUTOMATA’23 (Exploratory Papers), 2023. DOI-link   PDF-link
  6. Roget, Mathieu, Hachem Kadri, and Giuseppe Di Molfetta. “Optimality Conditions for Spatial Search with Multiple Marked Vertices.” Physical Review Research 5 (July 2023). DOI-link   PDF-link
  7. Perrotin, Pacôme, and Sylvain Sené. “Turning Block-Sequential Automata Networks into Smaller Parallel Networks with Isomorphic Limit Dynamics.” In Proceedings of CiE’2023, 13967:214–28. LNCS. Springer, 2023. DOI-link   PDF-link
  8. Jolly, Nicolas, and Giuseppe Di Molfetta. “Twisted Quantum Walks, Generalised Dirac Equation and Fermion Doubling.” The European Physical Journal D 77 (May 2023): 80. DOI-link   arXiv-link  
  9. Siegel, Pierre, Andrei Doncescu, Vincent Risch, and Sylvain Sené. “Representation of Gene Regulation Networks by Hypothesis Logic-Based Boolean.” The Journal of Supercomputing 79 (March 2023): 4556–81. DOI-link   PDF-link

2022

  1. Perrot, Kévin, and S. Sené. “Les Réseaux d’Automates Booléens Au Cœur Du Calcul Naturel.” 1024 – Bulletin De La Socété Informatique De France 20 (November 2022): 171–82. DOI-link   PDF-link
  2. Paulevé, Loïc, and Sylvain Sené. “Boolean Networks and Their Dynamics: the Impact of Updates.” (Chapter) Systems Biology Modelling and Analysis: Formal Bioinformatics Methods and Tools, November 2022, 173–250. DOI-link   PDF-link
  3. Kari, Jarkko, and Victor H. Lutfalla. Natural Computing, September 2022. DOI-link   arXiv-link   
    @article{kl2022,
  author = {Kari, Jarkko and Lutfalla, Victor H.},
  %title = {{Planar Rosa: a family of quasiperiodic substitution discrete plane tilings with 2n-fold rotational symmetry}},
  journal = {Natural Computing},
  month = sep,
  year = {2022},
  doi = {10.1007/s11047-022-09929-8},
  eprint = {2203.08856}
}
  4. Sellapillay, Kevissen, Alberto D Verga, and Giuseppe Di Molfetta. “Entanglement Dynamics and Ergodicity Breaking in a Quantum Cellular Automaton.” Physical Review B 106, no. 10 (September 2022): 104309. arXiv-link  
  5. Zylberman, Julien, Giuseppe Di Molfetta, Marc Brachet, Nuno F. Loureiro, and Fabrice Debbasch. “Quantum Simulations of Hydrodynamics via the Madelung Transformation.” Physical Review A 106, no. 3 (September 2022): 032408. arXiv-link  
  6. Balbi, Pedro Paulo, Enrico Formenti, Kévin Perrot, Sara Riva, and Eurico L. P. Ruivo. “Non-Maximal Sensitivity to Synchronism in ECA: Exact Asymptotic Measures.” Theoretical Computer Science 926 (August 2022): 21–50. DOI-link   arXiv-link  
  7. Roget, Mathieu, Giuseppe Di Molfetta, and Hachem Kadri. “Quantum Perceptron Revisited: Computational-Statistical Tradeoffs.” In Proceedings of UAI’2022, 1697–1706. PMLR, 2022. arXiv-link  
  8. Di Molfetta, Giuseppe, and Victor Deng. “Geodesic Quantum Walks.” Physical Review A 105, no. 6 (June 2022): 062420. DOI-link   arXiv-link  
  9. Bridoux, Florian, Amélia Durbec, Kévin Perrot, and Adrien Richard. “Complexity of Fixed Point Counting Problems in Boolean Networks.” Journal of Computer and System Sciences 126 (June 2022): 138–64. DOI-link   arXiv-link  
  10. Nguyen, Viet-Ha, and Kévin Perrot. “Rikudo Is NP-Complete.” Theoretical Computer Science 910 (April 2022): 34–47. DOI-link   arXiv-link  
  11. Demongeot, Jacques, Tarek Melliti, Mathilde Noual, Damien Regnault, and Sylvain Sené. “On Boolean Automata Isolated Cycles and Tangential Double-Cycles Dynamics.” (Chapter) Automata and Complexity: Essays Presented to Eric Goles on the Occasion of His 70th Birthday, Springer Series on Emergence, Complexity and Computation 42 (April 2022): 145–78. DOI-link   arXiv-link  
  12. Fersula, Jérémy, Camille Noûs, and Kévin Perrot. “Sandpile Toppling on Penrose Tilings: Identity and Isotropic Dynamics.” (Chapter) Automata and Complexity: Essays Presented to Eric Goles on the Occasion of His 70th Birthday, Springer Series on Emergence, Complexity and Computation 42 (April 2022): 117–43. DOI-link   arXiv-link  
  13. Perrot, Kévin. “On the Complexity of Counting Feedback Arc Sets.” Chicago Journal of Theoretical Computer Science 2022 (March 2022). DOI-link   arXiv-link   PDF-link
  14. Sellapillay, Kevissen, Pablo Arrighi, and Giuseppe Di Molfetta. “A Discrete Relativistic Spacetime Formalism for 1+1-QED with Continuum Limits.” Scientific Reports 12 (February 2022): 2198. DOI-link   arXiv-link  
  15. Perrot, Kévin. “Études De La Complexité Algorithmique Des Réseaux d’Automates.” Aix-Marseille Université, January 2022. Habilitation à diriger des recherches.   PDF-link
  16. Arrighi, Pablo, Giuseppe Di Molfetta, and Nathanaël Eon. “Gauge-Invariance in Cellular Automata.” Natural Computing, January 2022. DOI-link   arXiv-link  
  17. Bridoux, Florian. “Sequentialization and Procedural Complexity in Automata Networks.” Theoretical Computer Science 898 (January 2022): 92–109. DOI-link   HAL-link  

2021

  1. Goles, Eric, Diego Maldonado, Pedro Montealegre, and Martín Ríos Wilson. “On the Complexity of Asynchronous Freezing Cellular Automata.” Information and Computation 281 (December 2021): 104764. DOI-link   arXiv-link  
  2. Goles, Eric, Andrew Adamatzky, Pedro Montealegre, and Martín Ríos Wilson. “Generating Boolean Functions on Totalistic Automata Networks.” International Journal of Unconventional Computing 16 (November 2021): 343–91. arXiv-link  
  3. Kari, Jarkko, and Étienne Moutot. “Decidability and Periodicity of Low Complexity Tilings.” Theory of Computing Systems, October 2021. DOI-link   arXiv-link  
  4. Arrighi, Pablo, Marin Costes, and Nathanäel Eon. “Universal Gauge-Invariant Cellular Automata.” In Proceedings of MFCS’21, 202:9:1–9:14. LIPIcs. Schloss Dagstuhl Publishing, 2021. DOI-link   arXiv-link   PDF-link
  5. Perrot, Kévin, Pacôme Perrotin, and Sylvain Sené. “On Boolean Automata Networks (De)Composition.” Fundamenta Informaticae 181 (August 2021): 163–88. DOI-link   PDF-link
  6. Goles, Eric, Pedro Montealegre, Martín Ríos Wilson, and Guillaume Theyssier. “On the Impact of Treewidth in the Computational Complexity of Freezing Dynamics.” In Proceedings of CiE’21, 12813:260–72. LNCS. Springer, 2021. DOI-link   arXiv-link  
  7. Paulevé, Loïc, and Sylvain Sené. “Non-Deterministic Updates of Boolean Networks.” In Proceedings of AUTOMATA’21, 90:10:1–10:16. OASIcs. Schloss Dagstuhl Publishing, 2021. DOI-link   arXiv-link  
  8. Castillo-Ramirez, Alonso, Pierre Guillon, and Kévin Perrot, eds. Proceedings of AUTOMATA’21. Vol. 90. OASIcs. Schloss Dagstuhl Publishing, 2021.
  9. Durbec, Amélia. “Graph Subshifts.” In Proceedings of AUTOMATA’21 (Exploratory Papers), 4:1–4:11, 2021. HAL-link  
  10. Perrotin, Pacôme. “Associating Parallel Automata Network Dynamics and Strictly One-Way Cellular Automata.” In Proceedings of AUTOMATA’21 (Exploratory Papers), 8:1–8:15, 2021. HAL-link  
  11. Ríos Wilson, Martín. “On Automata Networks Dynamics: an Approach Based on Computational Complexity Theory.” PhD thesis, Aix-Marseille Université & Universidad de Chile, 2021. PDF-link
  12. Goles, Eric, Pedro Montealegre, and Kévin Perrot. “Freezing Sandpiles and Boolean Threshold Networks: Equivalence and Complexity.” Advances in Applied Mathematics 125 (April 2021): 102161. DOI-link   arXiv-link  
  13. Duranthon, Odilon, and Giuseppe Di Molfetta. “Coarse-Grained Quantum Cellular Automata.” Physical Review A 103 (March 2021): 032224. DOI-link   arXiv-link  
  14. Gamard, Guilhem, Pierre Guillon, Kévin Perrot, and Guillaume Theyssier. “Rice-like Theorems for Automata Networks.” In Proceedings of STACS’21, 187:32:1–32:17. LIPIcs. Schloss Dagstuhl Publishing, 2021. DOI-link   PDF-link
  15. Perrot, Kévin, Pacôme Perrotin, and Sylvain Sené. “Optimising Attractor Computation in Boolean Automata Networks.” In Proceedings of LATA’21, 12638:68–80. LNCS. Springer, 2021. DOI-link   arXiv-link  
  16. Manighalam, Michael, and Giuseppe Di Molfetta. “Continuous Time Limit of the DTQW in 2D+1 and Plasticity.” Quantum Information Processing 20 (February 2021): 76. DOI-link   arXiv-link  
  17. Bridoux, Florian, Caroline Gaze-Maillot, Kévin Perrot, and Sylvain Sené. “Complexity of Limit-Cycle Problems in Boolean Networks.” In Proceedings of SOFSEM’21, 12607:135–46. LNCS. Springer, 2021. DOI-link   arXiv-link  
  18. Perrotin, Pacôme. “Simulation Entre Modèles De Calcul Naturel Et Modularité Des Réseaux d’Automates.” PhD thesis, Aix-Marseille Université, 2021. PDF-link
  19. Bérenger, Cédric. “Grands Réseaux Maillés Basse Énergie: Protocoles Minimalistes Pour La Synchronisation, La Mesure De Distance Et Le Partitionnement.” PhD thesis, Aix-Marseille Université, 2021.

2020

  1. Di Molfetta, Giuseppe. “Quantum Walks, Limits and Transport Equations.” Aix-Marseille Université, December 2020. Habilitation à diriger des recherches.   PDF-link
  2. Bridoux, Florian, Maximilien Gadouleau, and Guillaume Theyssier. “Expansive Automata Networks.” Theoretical Computer Science 843 (December 2020): 25–44. DOI-link   arXiv-link  
  3. Roget, Mathieu, Basile Herzog, and Giuseppe Di Molfetta. “Quantum Control Using Quantum Memory.” Scientific Reports 10 (December 2020): 21354. DOI-link   arXiv-link  
  4. Perrot, Kévin, and Éric Rémila. “On the Emergence of Regularities on One-Dimensional Decreasing Sandpiles.” Theoretical Computer Science 843 (December 2020): 1–24. DOI-link  
  5. Leporati, Alberto, Luca Manzoni, Mauri Giancarlo, Antonio E. Porreca, and Claudio Zandron. “Simulating Counting Oracles with Cooperation.” Journal of Membrane Computing 2 (December 2020): 303–10. DOI-link   PDF-link
  6. Di Molfetta, Giuseppe, and Basile Herzog. “Searching via Nonlinear Quantum Walk on the 2D-Grid.” Algorithms 13 (November 2020): 305. DOI-link   arXiv-link  
  7. Goles, Eric, Pedro Montealegre, and Martín Ríos Wilson. “On the Effects of Firing Memory in the Dynamics of Conjunctive Networks.” Discrete and Continuous Dynamical Systems 40 (October 2020): 5765–93. DOI-link   PDF-link
  8. Ferretti, Claudio, Alberto Leporati, Luca Manzoni, and Antonio E. Porreca. “The Many Roads to the Simulation of Reaction Systems.” Fundamenta Informaticae 171 (October 2020): 175–88. DOI-link   arXiv-link  
  9. Perrot, Kévin, Pacôme Perrotin, and Sylvain Sené. “On the Complexity of Acyclic Modules in Automata Networks.” In Proceedings of TAMC’20, 12337:168–80. LNCS. Springer, 2020. DOI-link   arXiv-link  
  10. Balbi, Pedro P., Enrico Formenti, Kévin Perrot, Sara Riva, and Eurico L. P. Ruivo. “Non-Maximal Sensitivity to Synchronism in Periodic Elementary Cellular Automata: Exact Asymptotic Measures.” In Proceedings of AUTOMATA’20, 12286:14–28. LNCS. Springer, 2020. DOI-link   arXiv-link  
  11. Manzoni, Luca, Antonio E. Porreca, and Grzegorz Rozenberg. “Facilitation in Reaction Systems.” Journal of Membrane Computing 2 (October 2020): 149–61. DOI-link   PDF-link
  12. Ruivo, Eurico L. P., Pedro Paulo Balbi, Marco Montalva-Medel, and Kévin Perrot. “Maximum Sensitivity to Update Schedules of Elementary Cellular Automata over Infinite Configurations.” Information and Computation 274 (October 2020): 104538. DOI-link  
  13. Formenti, Enrico, and Kévin Perrot. “How Hard Is It to Predict Sandpiles on Lattices? A Survey.” Fundamenta Informaticae 171 (October 2020): 189–219. DOI-link   arXiv-link  
  14. Bridoux, Florian, Maximilien Gadouleau, and Guillaume Theyssier. “Commutative Automata Networks.” In Proceedings of AUTOMATA’20, 12286:43–58. LNCS. Springer, 2020. DOI-link   arXiv-link  
  15. Casalé, Balthazar, Giuseppe Di Molfetta, Hachem Kadri, and Liva Ralaivola. “Quantum Bandits.” Quantum Machine Intelligence 2 (August 2020): 11. DOI-link   arXiv-link  
  16. Nguyen, Viet-Ha, Kévin Perrot, and Mathieu Vallet. “NP-Completeness of the Game Kingdomino TM.” Theoretical Computer Science 822 (June 2020): 23–35. DOI-link   arXiv-link  
  17. Bridoux, Florian, Maximilien Gadouleau, and Guillaume Theyssier. “On Simulation in Automata Networks.” In Proceedings of CiE’20, 12098:277–88. LNCS. Springer, 2020. DOI-link   arXiv-link  
  18. Perrot, Kévin, Sylvain Sené, and Lucas Venturini. “#P-Completeness of Counting Update Digraphs, Cacti, and Series-Parallel Decomposition Method.” In Proceedings of CiE’20, 12098:326–38. LNCS. Springer, 2020. DOI-link   arXiv-link  
  19. Bridoux, Florian, Alonso Castillo-Ramirez, and Maximillien Gadouleau. “Complete Simulation of Automata Networks.” Journal of Computer and System Sciences 109 (May 2020): 1–21. DOI-link   arXiv-link  
  20. Roget, Mathieu, Stéphane Guillet, Pablo Arrighi, and Giuseppe Di Molfetta. “Grover Search as a Naturally Occurring Phenomenon.” Physical Review Letters 124 (May 2020): 180501. DOI-link   arXiv-link  
  21. Goles, Eric, Fabiola Lobos, Gonzalo A. Ruz, and Sylvain Sené. “Attractor Landscapes in Boolean Networks with Firing Memory.” Natural Computing 19 (May 2020): 295–319. DOI-link   PDF-link
  22. Arnault, Pablo, Adrian Macquet, Andreu Anglès Castillo, Iván Márquez Martín, Vicente Pina Canelles, Armando Pérez, Giuseppe Di Molfetta, Pablo Arrighi, and Fabrice Debbasch. “Quantum Simulation of Quantum Relativistic Diffusion via Quantum Walks.” Journal of Physics A: Mathematical and Theoretical 53 (April 2020): 205303. DOI-link   arXiv-link  
  23. Jnane, Hamza, Giuseppe Di Molfetta, and Filippo M. Miatto. “Growing Random Graphs with Quantum Rules.” In Proceedings of QSQW’20, 315:38–47. EPTCS, 2020. DOI-link   arXiv-link  
  24. Di Molfetta, Giuseppe, Vivien Kendon, and Yutaka Shikano, eds. Proceedings of QSQW’20. Vol. 315. EPTCS, 2020. arXiv-link  
  25. Leporati, Alberto, Luca Manzoni, Mauri Giancarlo, Antonio E. Porreca, and Claudio Zandron. “A Turing Machine Simulation by P Systems without Charges.” Journal of Membrane Computing 2 (February 2020): 71–79. DOI-link   arXiv-link  
  26. ———. “Shallow Laconic P Systems Can Count.” Journal of Membrane Computing 2 (February 2020): 49–58. DOI-link   PDF-link
  27. Aristote, Quentin, Nathanaël Eon, and Giuseppe Di Molfetta. “Dynamical Triangulation Induced by Quantum Walk.” Symmetry 12 (January 2020): 128. DOI-link   arXiv-link  
  28. Arrighi, Pablo, Simon Martiel, and Simon Perdrix. “Reversible Causal Graph Dynamics: Invertibility, Block Representation, Vertex-Preservation.” Natural Computing 19 (January 2020): 157–78. DOI-link  
  29. Perrot, Kévin, Marco Montalva-Medel, Pedro P. B. de Oliveira, and Eurico L. P. Ruivo. “Maximum Sensitivity to Update Schedule of Elementary Cellular Automata over Periodic Configurations.” Natural Computing 19 (January 2020): 51–90. DOI-link   HAL-link  
  30. Demongeot, Jacques, and Sylvain Sené. “About Block-Parallel Boolean Networks: a Position Paper.” Natural Computing 19 (January 2020): 5–13. DOI-link   PDF-link
  31. Formenti, Enrico, and Sylvain Sené, eds. Automata Networks and Their Applications. Vol. 19. Natural Computing. Springer, 2020. DOI-link   PDF-link
  32. Arrighi, Pablo, Cédric Bény, and Terry Farrelly. “A Quantum Cellular Automaton for One-Dimensional QED.” Quantum Information Processing 19 (January 2020): 88. DOI-link   arXiv-link  
  33. Di Molfetta, Giuseppe, and Pablo Arrighi. “A Quantum Walk with Both a Continuous-Time Limit and a Continuous-Spacetime Limit.” Quantum Information Processing 19 (January 2020): 47. DOI-link   arXiv-link  
  34. Gaze-Maillot, Caroline, and Antonio E. Porreca. “Profiles of Dynamical Systems and Their Algebra,” 2020. arXiv-link  

2019

  1. Márquez Martín, Ivan. “Quantum Walks: Background Geometry and Gauge Invariance.” PhD thesis, Aix-Marseille Université & Universidad de Valencia, 2019. PDF-link
  2. Pires, Marcelo A., Giuseppe Di Molfetta, and Sílvio M. Duarte Queirós. “Multiple Transitions between Normal and Hyperballistic Diffusion in Quantum Walks with Time-Dependent Jumps.” Scientific Reports 9, no. 1 (December 2019): 19292. arXiv-link  
  3. Arrighi, Pablo, Giuseppe Di Molfetta, and Nathanaël Eon. “Non-Abelian Gauge-Invariant Cellular Automata.” In Proceedings of TPNC’19, 11934:211–21. LNCS. Springer, 2019. DOI-link   arXiv-link  
  4. Arrighi, Pablo, Simon Martiel, and Simon Perdrix. “Reversible Causal Graph Dynamics: Invertibility, Block Representation, Vertex-Preservation.” Natural Computing, October 2019. DOI-link  
  5. Vilchis Medina, José Luis, Pierre Siegel, Vincent Risch, and Andrei Doncescu. “A Resilient Behavior Approach Based on Non-Monotonic Logic.” In Proceedings of MICAI’19, 11835:403–13. LNCS. Springer, 2019. DOI-link   PDF-link
  6. Arrighi, Pablo. “An Overview of Quantum Cellular Automata.” Natural Computing 18, no. 4 (September 2019): 885–99. DOI-link   arXiv-link  
  7. Vilchis Medina, José Luis, Pierre Siegel, Vincent Risch, and Andrei Doncescu. “An Implementation of a Non-Monotonic Logic in an Embedded Computer for a Motor-Glider.” In Proceedings of ICLP’19 (Technical Communications), 306:323–29. EPTCS. Open Publishing Association, 2019. DOI-link   arXiv-link  
  8. Arrighi, Pablo, Cédric Bény, and Terry Farrelly. “A Quantum Cellular Automaton for One-Dimensional QED.” In Local Proceedings of AQIS’19, 2019. arXiv-link  
  9. Dennunzio, Alberto, Enrico Formenti, Luca Manzoni, and Antonio E. Porreca. “Complexity of the Dynamics of Reaction Systems.” Information and Computation 267 (August 2019): 96–109. DOI-link   arXiv-link  
  10. Arrighi, Pablo, Giuseppe Di Molfetta, Iván Márquez Martín, and Armando Pérez. “From Curved Spacetime to Spacetime-Dependent Local Unitaries over the Honeycomb and Triangular Quantum Walks.” Scientific Reports 9 (July 2019): 10904. DOI-link   arXiv-link  
  11. Bridoux, Florian. “Simulations Intrinsèques Et Complexités Dans Les Réseaux d’Automates.” PhD thesis, Aix-Marseille Université, 2019. PDF-link
  12. Bridoux, Florian, Nicolas Durbec, Kévin Perrot, and Adrien Richard. “Complexity of Maximum Fixed Point Problem in Boolean Networks.” In Proceedings of CiE’19, 11558:132–43. LNCS. Springer, 2019. DOI-link   PDF-link
  13. Dennunzio, Alberto, Enrico Formenti, Luca Manzoni, Luciano Margara, and Antonio E. Porreca. “On the Dynamical Behaviour of Linear Higher-Order Cellular Automata and Its Decidability.” Information Sciences 486 (June 2019): 73–87. DOI-link   arXiv-link  
  14. Arrighi, Pablo, Nicolas Durbec, and Aurélien Emmanuel. “Reversibility vs Local Creation/Destruction.” In Proceedings of RC’19, 11497:51–66. LNCS. Springer, 2019. DOI-link   arXiv-link  
  15. Leporati, Alberto, Luca Manzoni, Giancarlo Mauri, Antonio E. Porreca, and Claudio Zandron. “Characterizing PSPACE with Shallow Non-Confluent P Systems.” Journal of Membrane Computing 1, no. 2 (April 2019): 75–84. DOI-link   arXiv-link  
  16. Arnault, Pablo, Armando Pérez, Pablo Arrighi, and Terry Farrelly. “Discrete-Time Quantum Walks as Fermions of Lattice Gauge Theory.” Physical Review A 99 (March 2019): 032110. DOI-link   arXiv-link  
  17. Hatifi, Mohamed, Giuseppe Di Molfetta, Fabrice Debbasch, and Marc Brachet. “Quantum Walk Hydrodynamics.” Scientific Reports 9, no. 1 (February 2019): 2989. DOI-link   PDF-link
  18. Dennunzio, Alberto, Enrico Formenti, Luca Manzoni, Luciano Margara, and Antonio E. Porreca. “Decidability of Sensitivity and Equicontinuity for Linear Higher-Order Cellular Automata.” In Proceedings of LATA’19, 11417:95–107. LNCS. Springer, 2019. DOI-link  
  19. Leporati, Alberto, Luca Manzoni, Giancarlo Mauri, Antonio E. Porreca, and Claudio Zandron. “Solving QSAT in Sublinear Depth.” In Proceedings of CMC’18, 11399:188–201. LNCS. Springer, 2019. DOI-link   arXiv-link  

2018

  1. Vilchis Medina, José Luis. “Modeling of Resilient Systems in Non-Monotonic Logic. Application to Solar Power UAV.” PhD thesis, Aix-Marseille Université, 2018. PDF-link
  2. Khaled, Tarek, Belaid Benhamou, and Pierre Siegel. “A New Method for Computing Stable Models in Logic Programming.” In Proceedings of ICTAI’18, 800–807. IEEE, 2018. DOI-link  
  3. Leporati, Alberto, Luca Manzoni, Giancarlo Mauri, Antonio E. Porreca, and Claudio Zandron. “A Turing Machine Simulation by P Systems without Charges.” In Proceedings of ACMC’18, 530:213–21. CDMTCS Research Report Series, 2018. arXiv-link  
  4. Vilchis Medina, José Luis, Pierre Siegel, Vincent Risch, and Andrei Doncescu. “Intelligent and Adaptive System Based on a Non-Monotonic Logic for an Autonomous Motor-Glider.” In Proceedings of IEEE ICARCV’18, 442–47. IEEE, 2018. DOI-link  
  5. Siegel, Pierre, Andrei Doncescu, Vincent Risch, and Sylvain Sené. “Towards a Boolean Dynamical System Representation in a Nonmonotonic Modal Logic.” In Proceedings of NMR’18, 53–62, 2018. PDF-link
  6. Márquez Martín, Iván, Pablo Arnault, Giuseppe Di Molfetta, and Armando Pérez. “Electromagnetic Lattice Gauge Invariance in Two-Dimensional Discrete-Time Quantum Walks.” Physical Review A 98, no. 3 (September 2018): 032333. DOI-link   arXiv-link  
  7. Arrighi, Pablo, Giuseppe Di Molfetta, and Stefano Facchini. “Quantum Walking in Curved Spacetime: Discrete Metric.” Quantum 2 (August 2018): 84. DOI-link   arXiv-link  
  8. Bérenger, Cédric, Peter Niebert, and Kévin Perrot. “Balanced Connected Partitioning of Unweighted Grid Graphs.” In Proceedings of MFCS’18, 117:39:1–39:18. LIPIcs. DROPS, 2018. DOI-link   PDF-link
  9. Ruivo, Eurico L. P., Marco Montalva-Medel, Pedro P. B. de Oliveira, and Kévin Perrot. “Characterisation of the Elementary Cellular Automata in Terms of Their Maximum Sensitivity to All Possible Asynchronous Updates.” Chaos, Solitons & Fractals 113 (August 2018): 209–20. DOI-link   PDF-link
  10. Demongeot, Jacques, and Sylvain Sené. “Phase Transitions in Stochastic Non-Linear Threshold Boolean Automata Networks on \MathbbZ^2: the Boundary Impact.” Advances in Applied Mathematics 98 (July 2018): 77–99. DOI-link   HAL-link  
  11. Ruz, Gonzalo A., Eric Goles, and Sylvain Sené. “Reconstruction of Boolean Regulatory Models of Flower Development Exploiting an Evolution Strategy.” In Proceedings of IEEE CEC’18, 1–8. IEEE, 2018. DOI-link   PDF-link
  12. Arrighi, Pablo, Giuseppe Di Molfetta, Iván Márquez Martín, and Armando Pérez. “Dirac Equation as a Quantum Walk over the Honeycomb and Triangular Lattices.” Physical Review A 97, no. 6 (June 2018): 062111. DOI-link   arXiv-link  
  13. Di Molfetta, Giuseppe, Diogo O. Soares-Pinto, and Sílvio M. Duarte Queirós. “Elephant Quantum Walk.” Physical Review A 97, no. 6 (June 2018): 062112. DOI-link   arXiv-link  
  14. Khaled, Tarek, Belaid Benhamou, and Pierre Siegel. “Une Nouvelle Méthode De Calcul De Modèles Stables En Programmation Logique.” In Proceedings of JFPC’18), 2018. PDF-link
  15. Noual, Mathilde, and Sylvain Sené. “Synchronism versus Asynchronism in Monotonic Boolean Automata Networks.” Natural Computing 17 (June 2018): 393–402. DOI-link   HAL-link  
  16. Arrighi, Pablo, Clément Chouteau, Stefano Facchini, and Simon Martiel. “Causal Dynamics of Discrete Manifolds.” In Proceedings of NCMA’18, 31–47. Österreichische Computer Gesellschaft, 2018. arXiv-link  
  17. Arrighi, Pablo, Giuseppe Di Molfetta, and Nathanaël Eon. “A Gauge-Invariant Reversible Cellular Automaton.” In Proceedings of AUTOMATA’18, 10875:1–12. LNCS. Springer, 2018. DOI-link   arXiv-link  
  18. Nguyen, Viet-Ha, and Kévin Perrot. “Any Shape Can Ultimately Cross Information on Two-Dimensional Abelian Sandpile Models.” In Proceedings of AUTOMATA’18, 10875:127–42. LNCS. Springer, 2018. DOI-link   arXiv-link  
  19. Perrot, Kévin, Pacôme Perrotin, and Sylvain Sené. “A Framework for (De)Composing with Boolean Automata Networks.” In Proceedings of MCU’18, 10881:121–36. LNCS. Springer, 2018. DOI-link   arXiv-link  
  20. Arrighi, Pablo, Simon Martiel, and Vincent Nesme. “Cellular Automata over Generalized Cayley Graphs.” Mathematical Structures in Computer Science 18, no. 3 (March 2018): 340–83. DOI-link   arXiv-link  
  21. Formenti, Enrico, Kévin Perrot, and Éric Rémila. “Computational Complexity of the Avalanche Problem for One Dimensional Decreasing Sandpiles.” Journal of Cellular Automata 13, no. 3 (March 2018): 215–28. arXiv-link  
  22. Goles, Eric, Pedro Montealegre, Kévin Perrot, and Guillaume Theyssier. “On the Complexity of Two-Dimensional Signed Majority Cellular Automata.” Journal of Computer and System Sciences 91 (February 2018): 1–32. DOI-link   HAL-link   PDF-link

2017

  1. Arrighi, Pablo, and Stefano Facchini. “Quantum Walking in Curved Spacetime: (3+1) Dimensions, and Beyond.” Quantum Information and Computation 17, no. 9-10 (August 2017): 0810–24. arXiv-link  
  2. Khaled, Tarek, Belaïd Benhamou, and Pierre Siegel. “Vers Une Nouvelle Méthode De Calcul De Modèles Stables Et Extensions En Programmation Logique.” In Proceedings of JIAF’17, 2017. PDF-link
  3. Siegel, Pierre, Andrei Doncescu, Vincent Risch, and Sylvain Sené. “Vers Une Représentation Des Systèmes Dynamiques Booléens En Logique Des Hypothèses.” In Proceedings of JIAF’17, 2017. HAL-link  
  4. Vilchis Medina, José-Luis, Pierre Siegel, and Andrei Doncescu. “Pilotage Stable d’Un Planeur En Utilisant Une Logique Non Monotone.” In Proceedings of JFPDA’17, 2017. HAL-link  
  5. Arrighi, Pablo, Alejandro Díaz-Caro, and Benoît Valiron. “The Vectorial λ-Calculus.” Information and Computation 254 (June 2017): 105–39. DOI-link   arXiv-link  
  6. Arrighi, Pablo, and Simon Martiel. “Quantum Causal Graph Dynamics.” Physical Review D 96, no. 2 (June 2017): 024026. DOI-link   arXiv-link  
  7. Montalva Medel, Marco, Kévin Perrot, Pedro de Oliveira, and Eurico Ruivo. “Sensitivity to Synchronism in Some Boolean Automata Networks.” In Proceedings of AUTOMATA’17 (Exploratory Papers), 2017. HAL-link  
  8. Márquez Martín, Iván, Giseppe Di Molfetta, and Armando Pérez. “Fermion Confinement via Quantum Walks in (2+1)-Dimensional and (3+1)-Dimensional Space-Time.” Physical Review A 95, no. 4 (April 2017): 042112. DOI-link   arXiv-link  
  9. Perrot, Kévin, and Éric Rémila. “Strong Emergence of Wave Patterns on Kadanoff Sandpiles.” Electronic Journal of Combinatorics 24, no. 2 (April 2017): P2.4. DOI-link   PDF-link
  10. Vilchis Medina, José-Luis, Pierre Siegel, and Andrei Doncescu. “Autonomous Aerial Vehicle Based on Non-Monotonic Logic.” In Proceedings of VEHITS’17, 236–41. ScitePress, 2017. DOI-link   HAL-link  
  11. Arrighi, Pablo, and Gilles Dowek. “Lineal: A Linear-Algebraic Lambda-Calculus.” Logical Methods in Computer Science 13, no. 1 (March 2017): 1–33. DOI-link   arXiv-link  
  12. Bridoux, Florian, Pierre Guillon, Kévin Perrot, Sylvain Sené, and Guillaume Theyssier. “On the Cost of Simulating a Parallel Boolean Automata Network with a Block-Sequential One.” In Proceedings of TAMC’17, 10185:112–28. LNCS. Springer, 2017. DOI-link   HAL-link   arXiv-link  
  13. Arrighi, Pablo, Vincent Nesme, and Reinhard F. Werner. “Bounds on the Speedup in Quantum Signaling.” Physical Review A 95, no. 1 (January 2017): 012331. DOI-link   arXiv-link  

2016

  1. Di Molfetta, Giuseppe, and Fabrice Debbasch. “Discrete-Time Quantum Walks in Random Artificial Gauge Fields.” Quantum Studies: Mathematics and Foundations 3 (December 2016): 293–311. DOI-link   arXiv-link  
  2. Alcolei, Aurore, Kévin Perrot, and Sylvain Sené. “On the Flora of Asynchronous Locally Non-Monotonic Boolean Automata Networks.” In Proceedings of SASB’15, 326:3–25. ENTCS. Elsevier, 2016. DOI-link   arXiv-link  
  3. Di Molfetta, Giuseppe, and Armando Pérez. “Quantum Walks as Simulators of Neutrino Oscillations in a Vacuum and Matter.” New Journal of Physics 18, no. 10 (October 2016): 103038. DOI-link   arXiv-link  
  4. Bru, Luis A., Germán J. de Valcárcel, Giuseppe Di Molfetta, Armando Pérez, Eugenio Roldán, and Fernando Silva. “Quantum Walk on a Cylinder.” Physical Review A 94, no. 3 (September 2016): 032328. DOI-link   arXiv-link  
  5. Arrighi, Pablo, Stefano Facchini, and Marcelo Forets. “Quantum Walking in Curved Spacetime.” Quantum Information Processing 15, no. 8 (August 2016): 3467–86. DOI-link   arXiv-link  
  6. Crespelle, Christophe, Tien-Nam Le, Kévin Perrot, and Thi Ha Duong Phan. “Linearity Is Strictly More Powerful than Contiguity for Encoding Graphs.” Discrete Mathematics 339, no. 8 (August 2016): 2168–77. DOI-link   arXiv-link  
  7. Melliti, Tarek, Damien Regnault, Adrien Richard, and Sylvain Sené. “Asynchronous Simulation of Boolean Networks by Monotone Boolean Networks.” In Proceedings of ACRI’16, 9863:182–91. LNCS. Springer, 2016. DOI-link   arXiv-link  
  8. Arnault, Pablo, Giuseppe Di Molfetta, Marc Brachet, and Fabrice Debbasch. “Quantum Walks and Non-Abelian Discrete Gauge Theory.” Physical Review A 94 (July 2016): 012335. DOI-link   arXiv-link  
  9. Arrighi, Pablo, Simon Martiel, and Simon Perdrix. “Reversible Causal Graph Dynamics.” In Proceedings of RC’2016, 9720:73–88. LNCS. Springer, 2016. DOI-link   arXiv-link  
  10. Nguyen, Thanh, Andrei Doncescu, and Pierre Siegel. “Performance Comparison of ADTree and Naive Bayes Algorithms for Spam Filtering.” World Academy of Science, Engineering and Technology 10, no. 5 (May 2016): 269–74. DOI-link  
  11. Arrighi, Pablo, and Gilles Dowek. “Free Fall and Cellular Automata.” In Proceedings of DCM’15, 204:1–10. EPTCS. Open Publishing Association, 2016. DOI-link   arXiv-link  
  12. Arrighi, Pablo, and Simon Perdrix. “Modèles De Calcul Quantiques.” In Informatique Mathématique - Une Photographie En 2016. CNRS Editions, 2016. PDF-link
  13. Perrot, Kévin, and Trung Van Pham. “Chip-Firing Game and Partial Tutte Polynomial for Eulerian Digraphs.” Electronic Journal of Combinatorics 23, no. 1 (March 2016): P1.57. DOI-link   arXiv-link  

2015

  1. Arrighi, Pablo, and Gilles Dowek. “Discrete Geodesics and Cellular Automata.” In Proceedings TPNC’2015, 9477:137–49. LNCS. Springer, 2015. DOI-link   arXiv-link  
  2. Fatès, Nazim, and Sylvain Sené, eds. Automates Cellulaires Et Réseaux d’Automates : Le Rôle Central De l’Irrégularité. Vol. 35. Technique Et Science Informatiques. Lavoisier, 2015.
  3. Melliti, Tarek, Mathilde Noual, Damien Regnault, and Sylvain Sené. “Cycles, Double-Cycles d’Interactions Et Modes De Mise à Jour – Une Synthèse.” Technique Et Science Informatiques 35 (November 2015): 401–30. PDF-link
  4. Perrot, Kévin, and Éric Rémila. “Piles De Sable Décroissantes 1D : Classification Expérimentale d’Émergences.” Technique Et Science Informatiques 34, no. 4 (November 2015): 377–400. HAL-link  
  5. Arrighi, Pablo, Simon Martiel, and Simon Perdrix. “Block Representation of Reversible Causal Graph Dynamics.” In Proceedings of FCT’2015, 9210:351–63. LNCS. Springer, 2015. DOI-link   PDF-link
  6. Melliti, Tarek, Mathilde Noual, Damien Regnault, Sylvain Sené, and Jérémy Sobieraj. “Asynchronous Dynamics of Boolean Automata Double-Cycles.” In Proceedings of UCNC’2015, 9252:250–62. LNCS. Springer, 2015. DOI-link   arXiv-link  
  7. Perrot, Kévin, and Éric Rémila. “Emergence on Decreasing Sandpile Models.” In Proceedings of MFCS’2015, 9234:419–31. LNCS. Springer, 2015. DOI-link   HAL-link  
  8. Doncescu, Andrei, and Pierre Siegel. “Emerging Trends in Computational Biology, Bioinformatics, and Systems Biology,” 409–527. Elsevier, 2015. PDF-link
  9. Arrighi, Pablo, and Simon Perdrix. “La Décohérence, Une Alliée Pour La Simulation.” La Recherche 501-502 (July 2015): 66–68. PDF-link
  10. Crespelle, Christophe, Tien-Nam Le, Kévin Perrot, and Thi Ha Duong Phan. “Linearity Is Strictly More Powerful than Contiguity for Encoding Graphs.” In Proceedings of WADS’2015, 9214:212–23. LNCS. Springer, 2015. DOI-link   arXiv-link  
  11. Perrot, Kévin, and Trung Van Pham. “Feedback Arc Set Problem and NP-Hardness of Minimum Recurrent Configuration Problem of Chip-Firing Game on Directed Graphs.” Annals of Combinatorics 19 (February 2015): 373–96. DOI-link   arXiv-link  

2014

  1. Barlovatz-Meimon, Georgia, and Sylvain Sené. “Culture De Cellules Animales (3e Édition),” 217–40. Lavoisier, 2014. PDF-link
  2. Perrot, Kévin, and Éric Rémila. “Emergence of Regularities on Decreasing Sandpile Models.” In Proceedings of 15th Mons Theoretical Computer Science Days, 2014. PDF-link
  3. Doncescu, Andrei, Pierre Siegel, and Tan Le. “Representation and Efficient Algorithms for the Study of Cell Signaling Pathways.” In Proceedings of ICAI’2014, 504–10, 2014. PDF-link
  4. ———. “Relevance of Information in Cell Signaling Pathways Using Default Logic.” In Proceedings of BIOCOMP’2014, 16–22. CSREA Press, 2014. PDF-link


Seminars

Subscribe to [cana-seminaire] mailing list.

You may also be interested in the seminars from
Groupe de travail - Informatique Quantique du LIS.

  • 03 décembre 2024 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘TBA’‘
    by Nicolas Schabanel (LIP,ENS Lyon)
    See abstract

    TBA

  • 26 novembre 2024 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Complete Equational Theories for Quantum circuits’‘
    by Alexandre Clément (Postdoc at LMF)
    See abstract

    An equational theory, for quantum circuits or for another graphical language, is a set of equations treated as non-oriented, local rewrite rules. It is said complete when it makes it possible to transform any two equivalent circuits into one another. Having a complete equational theory for quantum circuits can, in principle, help in designing procedures for circuit optimisation, hardware constraint satisfaction, or equivalence testing. From a more abstract perspective, this has a deeper meaning as this gives us an axiomatisation, which in some sense captures the behaviour of quantum circuits. Recently, I together with several collaborators found the first complete equational theory for (ancilla-free) quantum circuits. We further simplified it into just a few simple and intuitive equations, and we proved that this final set of equations is minimal, in the sense that none of the equations can be removed without loosing the completeness. The equational theory contains an equation schema involving an unbounded number of qubits, and we show that this cannot be avoided, although semantically the equations in question are essentially trivial, saying that a 2pi-rotation is the identity. On the contrary, when considering circuits with ancillae and/or qubit discarding, the equation schema can be derived from the other equations, leaving us with a complete equational theory made of equations acting on at most 3 qubits. I will present these results and in particular give the main ideas of the proof of completeness, which relies on a back-and-forth encoding between quantum circuits and another graphical language which was originally dedicated to linear optical circuits. I will also say a few words about some ongoing further work.

  • 12 novembre 2024 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Ants on the highway’‘
    by Victor Lutfalla (I2M)
    See abstract

    Langton’s ant is a very simple automaton whose asymptotic behaviour has been conjectured in the 80s but still evades formal proof. In this talk I will present recent advances on the asymptotic behaviour of generalized ants. Langton’s ant is a very simple automaton evolving with a binary configuration of the square grid. When the ant enters a white (or 0) cell it turns a left half-turn, flips the state of the cell and moves one step forward; when it enters a black (or 1) cell it turns a right half-turn, flips the state of the cell and moves one step forward. From the initial 0-uniform configuration, Langton’s ant has a " chaotic " transient phase during 10^4 steps, then enters a periodic behaviour with a drift: in 104 steps it moves by (± 2,± 2). This periodic behaviour with a drift is called highway. It has been conjectured that from any almost 0-uniform configuration (finitely many non-zero cells), Langton’s ant has the same behaviour : a " chaotic " transient phase and then the highway of period 104 and drift (± 2,± 2). A simple generalisation of Langton’s ant, takes a directing word w on alphabet L,R. The generalized ant w evolves with a square grid where the cells have states between 0 and |w|-1. When the ant w arrives on the cell in state k, if the k-th letter of w is a L it turns left (or right otherwise), increments the cell state by 1 modulo |w| and moves on step forward. We study the asymptotic behaviour of such generalized ants and in particular we prove that: - there exist infinite families of generalized ants with more than one possile highway behaviour - there exist ants with infinitely many different highway behaviours - in particular the " speed " of a highway of the ant w (on an almost-0-uniform configuration) is not determined by the directing word w

  • 05 novembre 2024 : 15h00 at online and TPR2/04.05 (Luminy)
    ‘‘Scalable Quantum Circuit Cutting in a Distributed System’‘
    by Shuwen Kan (Fordham University)
    Slides: PDF
    Video: see on AMUpod
    See abstract

    Despite rapid advancements in quantum computing, current systems remain limited by qubit count and quality. To address these limitations, recent efforts focus on multi-node quantum systems connecting smaller devices. While future approaches aim to leverage quantum channels for coupling, current methods primarily rely on circuit cutting techniques that leverage a hybrid quantum-classical system. It partitions large circuits into smaller, independently executable fragments and reconstructs them classically. However, existing methods face challenges such as increased search times with circuit complexity and inefficient resource allocation across multi-node systems. To address these issues, we introduce FitCut, a novel graph-based framework that employs a community-based, bottom-up strategy to identify optimal cut points based on resource constraints. Additionally, it incorporates a scheduling algorithm that optimizes resource allocation across workers. Implemented within the Qiskit framework, FitCut has been extensively evaluated, demonstrating significant improvements over existing tools such as the Qiskit Circuit Knitting Toolbox. Specifically, FitCut reduces search time by factors ranging from 3 to 2000 and enhances resource utilization rates by up to 388% on the worker side, resulting in a system-wide improvement of 286% in accumulated circuit depth.

  • 08 octobre 2024 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘A Framework for Universality in Physics, Computer Science, and Beyond’‘
    by Tomáš Gonda (University of Innsbruck)
    Slides: PDF
    Video: see on AMUpod
    See abstract

    Turing machines and spin models share a notion of universality according to which some simulate all others. We set up a categorical framework for universality which includes as instances universal Turing machines, universal spin models, NP completeness, top of a preorder, denseness of a subset, and others. By identifying necessary conditions for universality, we show that universal spin models cannot be finite. We also characterize when universality can be distinguished from a trivial one and use it to show that universal Turing machines are non-trivial in this sense. We leverage a Fixed Point Theorem inspired by a result of Lawvere to establish that universality and negation give rise to unreachability (such as uncomputability). As such, this work sets the basis for a unified approach to universality and invites the study of further examples within the framework.

  • 24 septembre 2024 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Recent advancements in consensus problems over automata networks’‘
    by Pacôme Perrotin (Universidade Presbiteriana Mackenzie)
    See abstract

    Consensus problems consider distributed systems (mostly cellular automata and automata networks) which are able to converge from any initial configuration to a uniform configuration, usually where the uniform value of the final configuration holds some information about the initial configuration. We present recent progress done in the last year regarding some variations of the problems, namely a new family of solutions to the parity and synchronisation problems in automata networks, and a cellular automata which solves the density problem using an intermediary alphabet and a sequential update schedule. We also discuss some recent negative results regarding the density problem, and some ongoing attempts at characterising all linear solutions to the parity problem.

  • 18 juillet 2024 : 16h00 at online and TPR2/04.05 (Luminy)
    ‘‘Complexity of the dynamics of resource-bounded reaction systems’‘
    by Rocco Ascone (PhD Università degli Studi di Trieste)
    Slides: PDF
    See abstract

    Reaction systems are discrete dynamical systems that model biological processes in living cells using finite sets of reactants, inhibitors, and products. Synchronous Boolean networks can be viewed as a generalisation of this model.

    In this talk, we will investigate the computational complexity of a comprehensive set of problems related to the existence of fixed points and attractors in three constrained classes of reaction systems: inhibitorless, reactantless and additive (in which each reaction involves at most one reactant and no inhibitors).

    We will see that although the absence of reactants or inhibitors simplifies the system’s dynamics, it does not always lead to a reduction in the complexity of the considered problems for inhibitorless/reactantless reaction systems. Furthermore, all considered problems are polynomially solvable in additive systems using a polynomially computable graph representation.

    I will also introduce some open questions and future research directions.

  • 18 juin 2024 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Les réseaux Booléens et leurs trapspaces’‘
    by Maximilien Gadouleau (Durham University)
    Slides: PDF
    See abstract

    Un réseau Booléen est un outil simple pour modéliser un réseau d’entités qui interagissent. Chaque entité a un état dans {0,1} qui évolue selon une règle déterministe. Mathématiquement, un réseau Booléen est une fonction f du cube {0,1}^n dans lui-même. Un “trapspace” d’un réseau Booléen f est un sous-cube clos par f. Les trapspaces sont importants car ils représentent des états stabilisés au cours de l’évolution du réseau. Un trapspace est dit principal s’il est le plus petit trapspace contenant une configuration x de {0,1}^n. Dans cet exposé, nous classifions les collections de trapspaces et les collections de trapspaces principaux des réseaux Booléens. Les trapspaces de f peuvent être représentés à l’aide d’un autre réseau, que l’on nomme réseau trapping. Nous montrons aussi que les réseaux trappings ont des propriétés dynamiques très intéressantes. Travaux en collaboration avec Loïc Paulevé et Sara Riva.

  • 04 juin 2024 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Nonclassicality in correlations without causal order’‘
    by Ravi Kunjwal (LIS)
    Video: see on AMUpod
    See abstract

    A Bell scenario can be conceptualized as a “communication” scenario with zero rounds of communication between parties, i.e., although each party can receive a system from its environment on which it can implement a measurement, it cannot send out any system to another party. Under this constraint, there is a strict hierarchy of correlation sets, namely, classical, quantum, and non-signalling. However, without any constraints on the number of communication rounds between the parties, they can realize arbitrary correlations by exchanging only classical systems. We consider a multipartite scenario where the parties can engage in at most a single round of communication, i.e., each party is allowed to receive a system once, implement any local intervention on it, and send out the resulting system once. Taking our cue from Bell nonlocality in the “zero rounds” scenario, we propose a notion of nonclassicality—termed antinomicity—for correlations in scenarios with a single round of communication. Similar to the zero rounds case, we establish a strict hierarchy of correlation sets classified by their antinomicity in single-round communication scenarios. Since we do not assume a global causal order between the parties, antinomicity serves as a notion of nonclassicality in the presence of indefinite causal order (as witnessed by causal inequality violations). A key contribution of this work is an explicit antinomicity witness that goes beyond causal inequalities, inspired by a modification of the Guess Your Neighbour’s Input (GYNI) game that we term the Guess Your Neighbour’s Input or NOT (GYNIN) game. Time permitting, I will speculate on why antinomicity is a strong notion of nonclassicality by interpreting it as an example of fine-tuning in classical models of indefinite causality.

  • 02 april 2024 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Solving the parity problem in automata networks’‘
    by Pedro Paulo Balbi (Universidade Presbiteriana Mackenzie)
    See abstract

    The parity problem is a classical binary benchmark for addressing the computational ability and limitations of automata networks. It refers to conceiving a local rule to allow deciding whether the number of 1-states in the nodes of an arbitrary network is an odd or even number, without global access to the nodes. In its standard formulation, the automata network has an odd number of nodes whose states, arranged as a cyclic configuration, should converge to a fixed point of all 0s, if the initial configuration has an even number of 1s, or to a fixed point of all 1s, otherwise. It has been shown that a local rule alone is able to solve the problem in this formulation. In this talk I will review some solutions available for the problem, with a focus on recent solutions we provided on a non-circulant graph with synchronous update.

  • 26 mars 2024 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Randomizing Boolean functions (informal discussion)’‘
    by Siamak Taati (American University of Beirut)
    See abstract

    I plan to discuss Boolean functions that turn biased random inputs into unbiased output. The main motivation is the study of the randomization phenomenon in cellular automata, which is then reduced to the study of the degree of permutiveness of the iterates of cellular automata. This is a work in progress. I can give an exposition of the aspects that may interest the audience, but would highly appreciate feedback and interactive discussions.

  • 19 mars 2024 : 14h00 at online and TPR2/04.05 (Luminy)
    ‘‘A noncommutative framework for quantum information theory and quantum programming’‘
    by Bert Lindenhovius (Researcher at the Slovak Academy of Sciences)
    See abstract

    Many quantum phenomena have classical counterparts, and are modeled by mathematical structures that are noncommutative generalizations of the mathematical structures that model these classical counterparts. Quantization is the process of finding such as noncommutative generalization, and relies heavily on the theory of operator algebras, i.e., algebras of continuous linear maps on a fixed Hilbert space. Operator algebras generalize complex-valued matrix algebras, and can be used to describe quantum systems beyond finite-level systems. We will discuss a relatively new quantization method, called discrete quantization, based on the concepts of quantum sets and quantum relations between them. Quantum sets are essentially (possibly infinite) sums of matrix algebras and form a class of operator algebras that generalize sets, whereas quantum relations are a kind of morphism between quantum sets generalizing binary relations between ordinary sets. We discuss how several structures relevant for quantum information theory such as the quantum hamming distance and quantum graphs can be understood via discrete quantization. Moreover, we will discuss quantum cpos, a noncommutative generalization of omega-complete partial orders (cpos), obtained via discrete quantization. Ordinary cpos are the main objects of study in domain theory, which is the underlying mathematical theory for the construction of mathematical models of programming languages in a structured way. In a similar way, we discuss how quantum cpos can be used for the construction of mathematical models of quantum programming languages in a structured way.

  • 19 mars 2024 : 10h00 at online and TPR2/04.05 (Luminy)
    ‘‘A categorical framework to study logical properties of systems and processes’‘
    by Nicolas Blanco (Postdoc at CEA)
    Video: see on AMUpod
    See abstract

    Categorical quantum mechanics and applied category theory are fields that study systems and processes by abstracting the main structures and properties of their models. A focus is put on compositionality: how to compose processes together and to describe complex systems from their subsystems. An important structure studied in these fields is given by compact closed categories. They correspond to models of one-to-one processes that can be sequentially composed (a category), where systems and processes can be composed in parallel (a tensor/monoidal product) and each system has a dual system that reverse the flow of information. Processes with many inputs and outputs can then be modelled as processes between the tensor product of the inputs and the tensor product of the outputs. Linear logic is a substructural logic where the information in a proof cannot be duplicated nor erased. That is, every hypothesis has to be used exactly once. It is closely connected to linear type theory through a Curry-Howard correspondence. Through categorical semantics one can study the structures and properties of its models. An important structure in this field is given by *-autonomous categories. These correspond to models of one-to-one proofs that can be sequentially composed (a category), where logical propositions can be composed in two ways, the conjunction and disjunction (two monoidal products, the tensor and the par), and where each proposition can be negated (a duality). Proofs with many hypotheses and many conclusions can then be modelled as proofs from the conjunction of the hypotheses to the disjunction of the conclusions. It turns out that a compact closed category is exactly a *-autonomous category where the two monoidal products coincide, i.e. the conjunction and disjunction have the same interpretation. This lead to a line of research exploring the connection between linear logic and quantum mechanics, amongst others. For example, Aleks Kissinger and Sander Uijlen showed that starting with a compact closed category modelling systems and processes, one can studied their causal structure logically by organising the causal systems and processes into a *-autonomous category. In this talk, I will consider these connections by adopting a slightly different perspective. Instead of considering one-to-one processes or proofs, I will take many-to-many ones as a primitive, in a structure called a polycategory. The monoidal products (and the duals) will then be recovered through a universal property akin to the one of the tensor products of vector spaces. This will determine the interpretation of the composition of systems or logical propositions uniquely, up-to unique isomorphism, instead of having it provided as extra data. Furthermore, it will make apparent another defining distinction between the compact closed and the *-autonomous models: in the latter the sequential composition is done along one specific object while in the former two processes can be composed along multiple systems. In particular compact closed categories allow for feedback and loops while *-autonomous categories don’t. I will then introduce bifibred polycategories explaining how they can be used to model the emergence of a logical framework structuring systems equipped with specific conditions. They are in part inspired by Hoare logic, a framework used in computer science to reason about and verify properties of programs. As an example, I will consider the case of finite dimensional Banach spaces and contractive polylinear maps. Finite dimensional vector spaces and polylinear maps will provide a model of systems and processes while the norms will be used to express conditions on states of the systems via (sub-)unitality. Another example is given by the aforementioned construction of causal structures. If time permits, I will present some research directions I am considering to extend this framework.

  • 12 mars 2024 : 14h00 at online and TPR2/04.05 (Luminy)
    ‘‘Quantum Information Processing with Gravitating Systems and More’‘
    by Aidan Chatwin-Davies (Okinawa Institute of Science and Technology)
    See abstract

    Quantum information theory quantifies the remarkable and surprising ways that quantum systems can be used to compute. Connecting the abstract theory to concrete physical systems often gives insight into a system’s physics; conversely, physical intuition can often inspire new ideas for information theory itself. This perspective has been particularly fruitful in quantum gravity, for which the essential question is to understand how gravitating systems store and process information. In this talk, we will explore how these two-way connections play out, in particular among quantum algorithms, quantum error correction, and gravitational holography. Time permitting, I will further discuss recent work that connects quantum error correction with areas of physics beyond gravity.

  • 28 février 2024 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Computable Aspects of Topological Spaces’‘
    by Djamel Eddine Amir (LORIA)
    See abstract

    The topological properties of a set have a strong impact on its computability properties. A striking illustration of this idea is given by spheres and closed manifolds : if a set X is homeomorphic to a sphere or a closed manifold, then any algorithm that semicomputes X in some sense can be converted into an algorithm that fully computes X. In other words, the topological properties of X enable one to derive full information about X from partial information about X. In that case, we say that X has computable type. Those results have been obtained by Miller and Iljazović and others in the recent years. We give a characterization of finite simplicial complexes having computable type using a local property of stars of vertices. Moreover, the reduction to homology implies that the computable type property is decidable, for finite simplicial complexes of dimension at most 4. We argue that the stronger, relativized version of computable type, is better behaved. Consequently, we obtain characterizations of strong computable type, related to the descriptive complexity of topological invariants. This leads us to investigate the expressive power of low complexity invariants in the Borel hierarchy and their ability to differentiate between spaces. Notably, we show that they are sufficient for distinguishing finite topological graphs.

  • 27 février 2024 : 14h00 at online and TPR2/04.05 (Luminy)
    ‘‘An implementable quantum algorithm for approximating geometric entanglement for pure states’‘
    by Niall Murphy (Equal1 Labs)
    See abstract

    Entanglement is a fundamental property of a quantum state that is a crucial differentiator between classical computation and quantum. Naturally, given its essential relevance to quantum algorithms and computation, there are many definitions of entanglement each with many classical methods to compute or approximate these values. Surprisingly, hardly any of these algorithms can be run on near term quantum hardware. In this work we introduce a new quantum algorithm to compute the geometric entanglement of multi-qubit pure states.

  • 20 février 2024 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Uniformly Chaotic Finite-Range Lattice Models’‘
    by Léo Gayral
    Slides: PDF
    Video: see on AMUpod
    See abstract

    L’étude de modèles de physique statistique permet aux mathématiques d’offrir un autre regard sur des phénomènes observables empiriquement. Un point d’intérêt est notamment le comportement de ces modèles lorsque la température tend vers 0, analogue à l’émergence de structures cristallines complexes dans des matériaux. En 2010, Chazottes et Hochman ont exhibé un potentiel tridimensionnel à interactions locales, pour lequel le système induit est chaotique, i.e. aucune trajectoire du système ne converge à température zéro. Dans cet exposé, on va s’intéresser plus en détail à la construction d’un modèle similairement chaotique, et permettant en outre un contrôle assez fin sur l’ensemble des valeurs d’adhérence des trajectoires. Pour ce faire, on introduira notamment une famille de pavages apériodiques, dont les propriétés combinatoires permettent de contrôler l’entropie, d’encoder des machines de Turing, de « simuler » des mesures de probabilité…

  • 6 février 2024 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Density of disc and sphere packings’‘
    by Daria Pchelina (LIP, ENS Lyon)
    Video: see on AMUpod
    See abstract

    How to stack an infinite number of oranges to maximize the proportion of the covered space? Kepler conjectured that the ``cannonball’ packing is an optimal way to do it. This conjecture took almost 400 years to prove, and the proof of Hales and Ferguson consists of 6 papers and tens of thousands of lines of computer code. Given an infinite number of coins of 3 fixed radii, how to place them on an infinite table to maximize the proportion of the covered surface? Triangulated disc packings are those where each “hole” is bounded by three pairwise tangent discs. Connelly conjectured that for the sets of disc radii where triangulated packings exist, one of them maximizes the proportion of the covered surface; this holds for unary and binary disc packings. In this talk, we will discuss various techniques used in the proof of the Kepler conjecture and other important results in the domain of disc and sphere packings. They allow us to prove the statement of the Connelly conjecture for 31 triangulated triplets of disc radii and disprove it for 45 other triplets. Besides that, we obtain tight bounds on the local density of simplicial cells in 2-sphere packings. Besides that, we will talk about some open questions of the domain in connection with tilings and computability.

  • 30 janvier 2024 : 14h00 at online and TPR2/04.05 (Luminy)
    ‘‘All You Need to Know about the Quantum Switch’‘
    by Hippolyte Dourdent (ICFO – Institut de Ciències Fotòniques, Barcelona)
    Slides: PDF
    See abstract

    While the standard formulation of quantum theory assumes a fixed background causal structure, the process matrix formalism allows to relax this assumption and explore the possibility of processes with indefinite causal orders. For example, one may imagine a quantum circuit in which the order between Alice and Bob’s operations on a target system is coherently controlled by another quantum system, such that their operations are in a superposition of causal orders. This so called “quantum switch” has already been shown to offer advantages in various information processing tasks. In this review, I will introduce the notion of causal nonseparability – formalizing the notion of indefinite causal orders – and its various certifications in a quantum switch. I will then give examples of applications for quantum information and present a crucial tool allowing to assess whether such advantages genuinely come from indefinite causal orders or not.

  • 23 janvier 2024 : 14h00 at online and TPR2/04.05 (Luminy)
    ‘‘Optimization in quantum information: from foundations to applications’‘
    by Martin Plávala (Universität Siegen)
    See abstract

    This talks investigates a class of common optimization problems in quantum information, semi-device-independent certification of Schmidt number of quantum states will be used as a specific example. Solutions to such problems will be presented as a byproduct of investigating the mathematical/foundational question whether entanglement exists in all non-classical operational theories. This problem was already considered as a mathematical problem by George Barker in the 70’ in the context of ordered vector spaces. As a consequence of this result, the need for mathematical tools to detect entanglement in all operational theories arises, we address this issue by presenting a generalization of the Doherty-Parrilo-Spedalieri (DPS) hierarchy to operational theories. Finally we discuss the unexpected applications of these results to solve initial problem of semi-device independent certification of Schmidt number of quantum states, for which we derive tight SDP hierarchy.

  • 16 janvier 2024 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Bootstrap percolation on Penrose tilings’‘
    by Victor Lutfalla (postdoc I2M)
    See abstract

    Penrose tilings are non-periodic tilings of the plane by two rhombuses up to isometry. Here we study dynamic percolation: a contamination process on Penrose tilings starting from a random initial configuration.

    Given a Penrose tiling we put a state 0 or 1 on each tile. On these configurations we run the Boostrap percolation cellular automaton: state 1 is stable and a 0 cell becomes 1 if it has (at least) two 1 neighbors. We say that a configuration percolates when its limit configuration is 1-uniform, i.e., when running the Bootstrap percolation cellular automaton on the configuration, every tile eventually gets contaminated. Denote B the set of configuration that percolate.

    We prove that for any Bernoulli measure μ (of positive parameter d) we have μ(B)=1. In other words, for any positive parameter d, if we pick an initial configuration c at random on a Penrose tiling following a Bernoulli distribution of parameter d the probability that c percolates is 1.

  • 9 janvier 2024 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘(Some) consequences of invasiveness in quantum mechanics’‘
    by Simon Milz (Trinity College Dublin)
    See abstract

    No physical system is every truly isolated from its surrounding environment. This particularly holds in quantum mechanics and leads to complex memory effects in the multi-time statistics of (quantum) stochastic processes. In contrast to the standard paradigm of classical stochastic processes, measurements in quantum mechanics are generally invasive, i.e., they change the state of the probed system, leading to a multitude of novel phenomena.

    In particular, invasiveness a priori stands in the way of a consistent quantum generalization of basic concepts used in the description of classical stochastic processes. In my talk, I will discuss how fundamental tenets of the theory of classical stochastic processes, like the Kolmogorov extension theorem (defining the notion of a stochastic process) and Markov order (defining the length/strength of memory) can meaningfully be recovered in quantum mechanics.

    Going beyond these generalizations of classical concepts, quantum memory possesses a much richer structure than its classical counterpart and affords for memory effects that do not exist in the classical world. I will discuss the instrument dependence of memory effects in quantum mechanics, as well as the possibility of hidden quantum memory, i.e., the existence of quantum processes with Markovian statistics that nonetheless fundamentally require memory for their implementation.

    Finally, invasiveness, one of the main ‘culprits’ for the complexity of quantum memory effects could, in principle, also be implemented in classical physics, putting in question the ‘quantumness’ of the aforementioned phenomena. By introducing the concept of ‘genuinely quantum processes’, I will however argue that, while an active choice in classical physics, invasiveness is a fundamentally unavoidable trait in quantum processes.

  • 19 décembre 2023 : 14h00 at online and TPR2/04.05 (Luminy)
    ‘‘Tightening continuity bounds on entropies and bounds on quantum capacities’‘
    by Michael G. Jabbour (Centre for Quantum Information and Communication, Université libre de Bruxelles)
    See abstract

    One of the most basic tasks in information theory is communication. The capacity of a quantum channel is the maximum rate at which information can be transmitted through it reliably (in the asymptotic limit) per use of the channel. Mathematically, the various definitions of capacities are expressed in terms of entropies. They are in general difficult to compute. However, they can be bounded with the help of continuity bounds on entropies. The latter are generally expressed in terms of a single distance measure between probability distributions or quantum states, typically, the total variation- or trace distance. However, if an additional distance measure is known, the continuity bounds can be significantly strengthened. Here, we prove a tight uniform continuity bound for the Shannon entropy in terms of both the local- and total variation distances. We also obtain a uniform continuity bound for the von Neumann entropy in terms of both the operator norm- and trace distances. We then apply our results to compute upper bounds on channel capacities. We first introduce (ε,ν)-degradable channels, which are ε-close in diamond norm and ν-close in completely bounded spectral norm to their complementary channel when composed with a degrading channel. This leads to improved upper bounds to the quantum- and private classical capacities of such channels. Moreover, these bounds can be further improved by considering certain unstabilized versions of the above norms. We show that upper bounds on the latter can be efficiently expressed as semidefinite programs. As an application, we obtain a new upper bound on the quantum capacity of the qubit depolarizing channel.

  • 12 décembre 2023 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Biological networks: from Boolean models in computational precision oncology to experimental neurosciences’‘
    by Célia Biane Fourati (Université de Bourgogne)
    See abstract

    Boolean dynamical models of biological signaling and transcriptional networks have been used these last years to model tumor cells and predict therapeutic targets in Cancer. Major limitations to a more generalised application of these types of models include:

    1. the step of models’ reconstruction that is currently done by manual curation of biological knowledge from the litterature by experts in molecular biology, which makes it a long process, dependent on the choices of the modeler and difficult to reproduce.

    2. The development of performing algorithmic methods allowing the reprogramming of the dynamical behavior of Boolean dynamical systems.

    In the course of this seminar, I will address the reconstruction of Boolean biological models from omics data, methods of reprogramming of dynamical behavior of dynamical systems and the application of such approaches to the discovery of new therapeutic targets in cancer. In a second part of the talk, I will introduce concepts from neurosciences and present recently published results on the integrative properties of cerebellar neurons.

  • 5 décembre 2023 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Projective characterization of higher-order quantum theory’‘
    by Timothée Hoffreumon (Centre for Quantum Information and Communication, Université libre de Bruxelles)
    See abstract

    Nesting transformations (or logic gates) is a common concept in computer science as some gates may depend on other gates. A typical example of this is the switch gate: it takes two gates as inputs and applies them on a target bit in an order controlled by another bit. Nothing forbids a priori to devise the analogous paradigm in quantum computing. But, contrastingly with the classical case, higher-order quantum transformations lead to the phenomenon of indefinite causal order (ICO) as previous works on the matter have shown. In the same way that a quantum state can be superposed between several values, hence indefinite, the order in which quantum transformations are applied on a quantum state can become superposed between several orderings, hence in ICO. For example, the quantum switch gate takes two transformations A and B as inputs and applies them on a target qubit in an order determined by a control qubit: if the control is 0, A then B are applied on the target; and if the control is 1, it is B then A. When the control qubit is in a superposed state, then the ordering becomes superposed between A then B and B then A.

    Therefore, extending quantum theory in a computer-science-motivated manner revealed ICO, a feature believed to be a prerogative of quantum gravity. In addition to this transversal aspect, ICO is also useful for practical purposes, as it was shown to provide an advantage for a variety of tasks in many fields such as quantum computing, information, metrology, and communications.

    The goal of this talk is to present a framework that formalizes and characterizes higher-order quantum theory. The two main questions answered are “Given an operator (which mathematically represents all kinds of quantum transformations), does it represent a higher-order transformation?” and “What is the underlying causal structure(s) of such an object?”. It extends two previous characterizations, one done using type theory, and the other one using category theory. This extension relies in particular on the use of superoperator projectors. These projectors have a twofold advantage: first, they make the characterization more straightforward as one can answer the first question simply by applying the projector corresponding to a given higher-order object on the operator. Second, they offer an intuitive explanation of the type-theoretic semantics of higher order: they are the algebraic rules for composing these projectors.

  • 28 novembre 2023 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Testing Spreading Behavior in Networks with Arbitrary Topologies’‘
    by Augusto Modanese (Aalto University)
    Slides: PDF
    Video: see on AMUpod
    See abstract

    Inspired by the works of Goldreich and Ron (J. ACM, 2017) and Nakar and Ron (ICALP, 2021), we initiate the study of property testing in dynamic environments with arbitrary topologies. Our focus is on the simplest non-trivial rule that can be tested, which corresponds to the 1-BP rule of bootstrap percolation and models a simple spreading behavior: Every “infected” node stays infected forever, and each “healthy” node becomes infected if and only if it has at least one infected neighbor. We show various results for both the case where we test a single time step of evolution and where the evolution spans several time steps. In the first, we show that the worst-case query complexity is O(Δ/ε) or Õ(√n/ε) (whichever is smaller), where Δ and n are the maximum degree of a node and number of vertices, respectively, in the underlying graph, and we also show lower bounds for both one- and two-sided error testers that match our upper bounds up to Δ=o(√n) and Δ=O(n^{1/3}), respectively. In the second setting of testing the environment over T time steps, we show upper bounds of O(Δ^{T−1}/εT) and Õ(|E|/εT), where E is the set of edges of the underlying graph. All of our algorithms are one-sided error, and all of them are also time-conforming and non-adaptive, with the single exception of the more complex Õ(√n/ε)-query tester for the case T=2.

  • 21 novembre 2023 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘The Many-Worlds Calculus: Representing Quantum Control’‘
    by Kostia Chardonnet (Università di Bologna)
    See abstract

    Résumé : We explore the interaction between two monoidal structures: a multiplicative one, for the encoding of pairing, and an additive one, for the encoding of choice. We propose a PROP to model computation in this framework, where the choice is parametrized by an algebraic side effect: the model can support regular tests, probabilistic and non-deterministic branching, as well as quantum branching, i.e. superposition. The graphical language comes equipped with a denotational semantics based on linear applications, and an equational theory. We prove the language to be universal, and the equational theory to be complete with respect to the semantics.

  • 14 novembre 2023 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘From reaction networks to Boolean networks: why and how’‘
    by Athénaïs Vaginay (ex CRAN/Loria)
    See abstract

    One way to get new insights about complex biological systems is to convert between modelling formalisms. Here, we deal with the conversion of reaction networks interpreted with the differential semantics, into Boolean networks. The conversion is particularly challenging, as it requires a drastic change in perspective: from a process-centred description with continuous time and values to a species-centred description with discrete steps and Boolean values. The conversion I present here is based on my PhD work. It aims at preserving properties from the input reaction network, such as its structure (the direct influences between the components) and its binarised transient dynamics (the transitions between the Boolean configurations). We will see how to extract the structure and dynamics of a reaction network, and how to use answer-set programming synthesise complying Boolean networks. So far, the evaluation of the approach on toy examples and real-world reaction networks from the repository BioModels, has demonstrated it effectiveness in synthesising Boolean networks complying with the input reaction networks. It also paved the way of the formal study of the relationship between the differential semantics of reaction network and Boolean networks. The perspectives mainly concern the practical relevance of the Boolean networks we synthesise, as well as the formal exploration of the relationship with other semantics of reaction networks.

  • 7 novembre 2023 : 14h00-16h00 at TPR2/04.05 (Luminy)
    ‘‘Introduction aux séries formelles 3’‘
    by Enrico Formenti (I3S, Sophia Antipolis)
    Slides: PDF
    See abstract

    Après quelques très brefs rappels sur les fonctions analytiques, nous allons regarder d’un peu plus près les notions de pôle et de singularité. Puis nous verrons comment ces deux dernières notions peuvent nous permettre d’étudier le comportement asymptotique des coefficients d’une série formelle.

  • 17 octobre 2023 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Towards Categorical Supermaps’‘
    by Matthew Wilson (University College London)
    See abstract

    In the last two decades, two new perspectives have gained traction in quantum foundations and quantum information theory; each case those perspectives call for a shift in focus from the states of the world to the transformations which act on them. The first perspective is the supermap (also known as process matrix) framework, which by treating standard physical transformations as objects to be manipulated by higher-order transformations, provides a formalisation of protocols in which processes are treated as resources and provides a framework for the analysis of indefinite causal structures. The second new perspective comes from the development of categorical quantum mechanics, which organises physical theories based on the background assumption that those theories always come with notions of transformations and their composition - in other words they form symmetric monoidal categories.

    In this talk, I will introduce monoidal categories and supermaps and discuss some key results and applications of both of these now-established perspectives. Next, I’ll discuss some motivations for putting them together and discuss the approaches we have recently used to do so, ultimately proposing a new formal definition of supermap for general theories of processes [1]. The main technical result I’ll discuss is a reconstruction of the standard definition of a supermap for both finite dimensional classical information theory, and for finite dimensional quantum information theory, derived from the proposed purely categorical (and physically well-motivated) definition.

    [1] Quantum Supermaps are Characterized by Locality: Matt Wilson, Giulio Chiribella, Aleks Kissinger

  • 10 octobre 2023 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Subsystem decompositions of quantum circuits and processes with indefinite causal order’‘
    by Julian Wechs (Centre for Quantum Information and Communication, Université libre de Bruxelles)
    Slides: PDF
    See abstract

    One can theoretically conceive of situations in which the causal order between quantum operations is no longer well-defined. Such causally indefinite processes are of interest from a foundational perspective, but could also open up new possibilities in quantum information, as they go beyond the conventional paradigm of quantum circuits. A central question is which of these processes have an operational interpretation or physical realisation, and, more particularly, whether indefinite causal order could be realised within standard physics. It has been shown that certain causally indefinite processes can take place as part of standard quantum mechanical evolutions, described by acyclic quantum circuits, if the latter are represented with respect to an alternative choice of quantum subsystems that can be delocalised in time. In this seminar, I will present a general framework to describe such transformations between different subsystem decompositions of quantum circuits. This puts the notion that indefinite causal order is realisable in standard quantum theory on a rigorous footing. Based on Nat. Commun. 14, 1471 and work in preparation.

  • 11 juillet 2023 : 11h00 at TPR2/04.05 (Luminy)
    ‘‘Une preuve du premier théorème d’incomplétude de Gödel avec la complexité de Kolmogorov’‘
    by Kévin Perrot (CANA)
    Slides: PDF
    See abstract

    Je propose de tenter cette preuve, due à Chaitin. Elle repose sur une formalisation du paradoxe de Berry : soit l’expression « le plus petit entier positif qui n’est pas définissable en moins de seize mots ». Cette expression définit cet entier en moins de seize mots, ce qui est paradoxal. Pour celles et ceux qui ne connaissent rien aux théorèmes d’incomplétude de Gödel et/ou à la calculabilité, je recommande de visionner les deux vidéos suivantes pour vous échauffer (10 minutes chacune) : https://www.arte.tv/fr/videos/097454-007-A/voyages-au-pays-des-maths et https://www.arte.tv/fr/videos/097454-005-A/voyages-au-pays-des-maths/. Ce séminaire n’attend aucun pré-requis de son auditoire, on pourra discuter de tout (en particulier de ce que disent les énoncés des théorèmes d’incomplétude de Gödel) et j’espère bien que vous aurez des questions pour m’aider à savoir quoi vous raconter (sinon, pour la preuve en elle-même, en 5 minutes c’est plié…).

  • 4 juillet 2023 : 10h00-12h00 at TPR2/04.05 (Luminy)
    ‘‘Introduction aux séries formelles 2’‘
    by Enrico Formenti (I3S, Sophia Antipolis)
    Slides: PDF
    See abstract

    Dans cette deuxième partie nous allons voir fonctions génératrices qui sont plutôt en forme de produit que de séries et nous verrons les liens profond qu’elles ont avec les partitions des entiers. Ensuite nous allons montrer comment utiliser les séries génératrices et les fonctions génératrices pour démontrer des identités, modéliser des problèmes inverses ou encore conter les mots d’un langage rationnel. In fine, nous allons introduire les séries formelles exponentielles ainsi qu’un formalisme pour décrire des familles d’ ‘objets structurés’. Nous montreront comment ce formalisme nous permet de compter ces familles d’objets (via les séries génératrices).

  • 20 juin 2023 : 14h00-16h00 at TPR2/04.05 (Luminy)
    ‘‘Introduction aux séries formelles 1’‘
    by Enrico Formenti (I3S, Sophia Antipolis)
    Slides: PDF
    See abstract

    Les séries formelles (SFs) sont un outil fondamental dans l’analyse combinatoire mais aussi dans l’analyse complexe. Dans ce cours/séminaire nous chercherons à donner un petit aperçu du rôle joué par les SFs dans des contextes assez différents. Le cours est donc structuré en plusieurs parties. Dans cette première partie nous parlerons de récurrences (linéaires et non) et montrerons comment les SFs puissent (dans certains cas) aider à trouver les termes généraux de ces récurrences. Nous montrerons aussi à l’occasion des liens avec les systèmes dynamiques discrets.

  • 30 mai 2023 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Trap spaces of Boolean networks are conflict-free siphons of their Petri net encoding’‘
    by Trinh Van-Giang (postdoc LIS)
    See abstract

    Boolean network modeling of gene regulation but also of post-transcriptomic systems has proven over the years that it can bring powerful analyses and corresponding insight to the many cases where precise biological data is not sufficiently available to build a detailed quantitative model. Besides simulation, the analysis of such models is mostly based on attractor computation, since those correspond roughly to observable biological phenotypes. The recent use of trap spaces made a real breakthrough in that field allowing to consider medium-sized models that used to be out of reach. However, with the continuing increase in model size and complexity of Boolean update functions, the state-of-the-art computation of minimal trap spaces based on prime-implicants shows its limits due to the difficulty of the prime-implicant computation. In this article we explore and prove for the first time a connection between trap spaces of a general Boolean network and siphons of its Petri net encoding. Besides important theoretical applications in studying properties of trap spaces, the connection enables us to propose an alternative approach to compute minimal trap spaces, and hence complex attractors, of a general Boolean network. It replaces the need for prime-implicants by a completely different technique, namely the enumeration of maximal siphons in the Petri net encoding of the original model. We then demonstrate its efficiency and compare it to the state-of-the-art methods on a large collection of real-world and randomly generated models.

  • 2 mai 2023 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘An asynchronous solution to the synchronisation problem for binary one-dimensional cellular automata’‘
    by Eurico Ruivo (Universidade Presbiteriana Mackenzie, Brazil)
    See abstract

    Because cellular automata rely on totally local and synchronous processing at the neighbourhood of each cell, the issue of global synchronisation of the cell states has a long tradition in cellular automata literature. In order to solve the synchronisation problem in periodic boundary condition, a rule needs to be conceived so as to lead any initial configuration to converge to a cyclic regime of period 2 characterised by all cells alternating between fully homogeneous configurations of 0s and 1s. In spite of its simplicity, the problem has been shown not to have a solution by synchronously updating the cell states. In contrast, we provide a solution to the problem, with a 4-neighbour rule, by replacing the synchronous update of the cells of the lattice with a deterministic, block sequential asynchronous update schedule.

  • 17 mars 2023 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Quantum algorithms for graph optimisations’‘
    by Simon Martiel (ATOS Quantum lab)
    See abstract

    Here his last results.

  • 13 mars 2023 : 14h00 at TPR2/05.37 (Luminy)
    ‘‘Generation and decomposition of dynamical systems’‘
    by Ekaterina Timofeeva (stagiaire LIS)
    See abstract

    During this seminar, we will provide an overview of our recent internship where we have completed the proof of correctness and complexity analysis a new polynomial-delay algorithm for generation of functional digraphs up to isomorphism. Our main objective was to contribute to the advancement of the semiring theory of dynamical systems. Additionally, we will discuss some of the findings we obtained while searching for counter-examples for the primality of dynamical systems. Finally, we will also present our attempt to use a SAT solver to expand the boundaries of the previously conducted experiments.

  • 28 février 2023 : 13h30 at TPR2/04.05 (Luminy)
    ‘‘Slow Invariant Manifolds of Slow–Fast Dynamical Systems’‘
    by Jean-Marc Ginoux (Institut Jules Verne, Université de Toulon)
    See abstract

    Slow–fast dynamical systems, i.e. singularly or nonsingularly perturbed dynamical systems possess slow invariant manifolds on which trajectories evolve slowly. Since the last century various methods have been developed for approximating their equations. This talk aims, on the one hand, to propose a classification of the most important of them into two great categories: singular perturbation-based methods and curvature-based methods, and on the other hand, to prove the equivalence between any methods belonging to the same category and between the two categories. Then, a deep analysis and comparison between each of these methods enable to state the efficiency of the Flow Curvature Method which is exemplified with paradigmatic Van der Pol singularly perturbed dynamical system and Lorenz slow–fast dynamical system.

    In his famous book entitled Theory of Oscillations, Nicolas Minorsky wrote: “each time the system absorbs energy the curvature of its trajectory decreases and vice versa”. By using the Flow Curvature Method, we establish that, in the ε-vicinity of the slow invariant manifold of generalized Liénard systems, the curvature of trajectory curve increases while the energy of such systems decreases. Hence, we prove Minorsky’s statement for the generalized Liénard systems. These results are then illustrated with the classical Van der Pol and generalized Liénard singularly perturbed systems.

    References

    Ginoux J.-M., 2021, “Slow Invariant Manifolds of Slow-Fast Dynamical Systems,” International Journal of Bifurcation and Chaos, Vol. 31(7) 2150112 (17 pages), 2021.

    Ginoux J.-M., Lebiedz D., Meucci R. & Llibre J., 2022, “Flow curvature manifold and energy of generalized Liénard systems,” Chaos Solitons & Fractals, 161, 112354 (7 pages), 2022.

  • 29 novembre 2022 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Category Theory for Quantum Natural Language Processing’‘
    by Alexis Toumi (LIS)
    Video: see on AMUpod
    See abstract

    Quantum natural language processing (QNLP) is the use of quantum computing to solve NLP tasks faster than any classical computer. In my PhD, I used category theory to implement QNLP models as homomorphisms from natural language grammar to parameterised quantum circuits. I will aim to explain my thesis from scratch, without assuming any knowledge of category theory, quantum computing or natural language processing: no equations, only diagrams! If time permits, I will give a demo of DisCoPy, the Python toolkit for computing with string diagrams which we used to run the first NLP experiments on quantum hardware. (See also Groupe de travail Informatique Quantique du LIS quantum.lis-lab.fr)

  • 22 novembre 2022 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Le problème du domino sur les sous-shifts de pavages par losanges’‘
    by Victor Lutfalla (GREYC, Caen)
    See abstract

    Un pavage est un recouvrement du plan par des tuiles qui ne se chevauchent pas. On appelle sous-shift un ensemble de pavages qui est invariant par translation et fermé (pour la topologie habituelle sur les pavages).

    Ici on s’intéresse au cas où il y a un nombre fini de tuiles à translation près, les tuiles sont des losanges, et à chaque fois que deux tuiles sont adjacentes elle partagent soit un unique sommet en commun soit une arête entière en commun.

    Sur ces pavages, on peut imposer des règles locales (à la manière des tuiles de Wang) en ajoutant des couleurs sur les arêtes des tuiles avec la règle que deux tuiles qui partagent une arête doivent avoir la même couleur pour cette arête. Dans ce cas, pour une même tuile géométrique, on peut avoir plusieurs copies avec des couleurs différentes sur les arêtes.

    Étant donné un sous-shift X de pavages par losanges, le problème du domino sur X prend en entrée un ensemble de règles locales F et renvoie Vrai si il existe un pavage de X qui respecte les règles locales F et Faux dans le cas contraire. Ce problème est indécidable et nous allons présenter une réduction du problème du domino sur un sous-shift de pavages par losanges depuis le problème du domino classique sur les tuiles de Wang.

  • 15 novembre 2022 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Curry-Howard: unveiling the computational content of proofs’‘
    by Étienne Miquey (I2M)
    Slides: PDF
    See abstract

    This talk is meant to be an introduction talk on the Curry-Howard correspondence between proofs and programs, for people that may not be dreaming about the λ-calculus every night. I will try to give an historical overview on why and how this correspondence was established, travelling back in time to see how the notion of “proof” evolved since the greeks (our historical lower bound in this talk) until becoming a major concept not only for mathematics but also for the development of programming languages (among other things). In between, I may talk about intuitionistic logic, proof assistants, realizability (my favorite topic), model theory, etc. This list is non-exhaustive, and in particular I would be glad to extend it with any related subsequent topic that may interest you (if so, you should send me an email: “Salut, je me suis toujours demandé ce que c’était qu’une théorie des types, tu pourrais en parler ?”, and I may try to include a slide or two, with a probability highly related to the date of your mail).

    Voici le code utilisé pour la démo : demo.v.

  • 8 novembre 2022 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘An electric circuit induced by quantum walks’‘
    by Mohamed Sabri (Tohoku University)
    See abstract

    In this talk, I will introduce the tailed model of quantum walks and some of its interesting results. Quantum walk is the quantum analogy of random walk. Unlike the usual quantum walks, the tailed model guarantees the convergence of the state of the walker to a stationary state. We are interested in utilizing this converging property. We consider the Grover dynamics with a specific initial state and we obtain the scattering of the dynamics in the long run. Based on the scattering matrix, we obtain a characterization of bipartite graphs. Moreover, we show that, if the underlying graph is (non-)bipartite, the stationary state expresses a (pseudo-)current function which satisfies (pseudo-)Kirchhoff laws. Furthermore, we introduce a quantum analogy of the electrical energy, called ‘comfortability’ and we show that the comfortability of the underlying graph can be expressed in terms of the geometric properties of the graph.

    (See also Groupe de travail Informatique Quantique du LIS quantum.lis-lab.fr)

  • 18 octobre 2022 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Contextuality in composite systems: entanglement vs. the Kochen-Specker theorem’‘
    by Ravi Kunjwal (Centre for Quantum Information and Communication, Université libre de Bruxelles)
    Video: see on AMUpod
    See abstract

    The Kochen-Specker (KS) theorem is often taken as a notion of nonclassicality that is independent of entanglement since it is provable on a three-dimensional Hilbert space. However, the smallest system on which both the KS theorem and entanglement are meaningful notions of nonclassicality is a two-qubit system. I will present some recent work on the necessity of entanglement in proofs of the KS theorem on multiqubit systems. We show two key results: firstly, that any proof of the KS theorem that uses KS sets necessarily requires entangled measurements, and secondly, that a statistical proof of the KS theorem with unentangled measurements on a multiqubit state exists if and only if this state can witness a Bell inequality violation. We also obtain an overall understanding of the relationship between unentangled Gleason and KS theorems on multiqudit systems in general. Time permitting, I will also discuss some implications of these results for the role of contextuality as a resource for multiqubit quantum computation with state injection. Based on arXiv:2109.13594.

  • 4 octobre 2022 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Interaction graphs of isomorphic automata networks’‘
    by Aymeric Picard Marchetto (PhD I3S, Sophia Antipolis)
    See abstract

    Given an automata network, many results show that some dynamical properties can be deduced from its interaction digraph. These dynamical properties are often invariant by isomorphism: number of fixed points, of images, length of limit cycles and transients… But the interaction digraph is not invariant by isomorphism: tow isomorphic automata networks (with the same alphabet and the same number of automata) can have very different interaction digraphs. In this talk, we study this phenomena. For that, given an automata network f with n automata, we denote by G[f] the set of interaction digraphs of automata networks isomorphic to f. Hence G[f] is a set of digraphs with n vertices. In particular, we show that if n>4, and f is neither the identity or constant, then G[f] contains the complete digraph. We also prove that G[f] always contains a digraph with minimum in-degree at most some constant that only depend on the alphabet size. Consequently, G[f] cannot only contain the complete digraph, but we show that there is f such that G[f] only contain digraphs with at least n^2/4 arcs. Finally, we prove that there is f such that G[f] contains all the digraphs with n vertices, excepted the empty one.

  • 19 juillet 2022 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Trois exemples magiques d’algorithmes randomisés’‘
    by Kévin Perrot (LIS)
    See abstract

    1) Compter jusqu’à 10^309 sur ses 10 doigts. 2) Obtenir un multiplicateur robuste à partir d’un multiplicateur foireux. 3) Preuves à divulgation nulle de connaissance (zéro-knowledge proofs). Ces exemples sont tirés de l’article ‘Randomness + determinism = progresses: Why random processes could be favored by evolution’ par Nicolas Schabanel en 2012.

  • 28 juin 2022 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘From global (color-blind) symmetry to local (gauge) invariance in cellular automata’‘
    by Nathanaël Eon (PhD LIS)
    See abstract

    In this talk, I will first introduce the concept of global (a.k.a. color-blind) and local (a.k.a. gauge) symmetries in cellular automata. The essence of those symmetries is for the cellular automata to be invariant under a change of the configuration, either done globally (applying the same transformation at every position) or locally (applying a different transformation at every position). Hence, a local symmetry is a priori stronger than a global one. In order to enforce the local symmetry, an extension of CA is introduced and an interesting equivalency result follows: globally symmetric CA are exactly those which can be extended into locally invariant ones (through a specific extension). Such result makes formal a folklore perspective in Physics which says that any local symmetry necessarily arise from an already existing global one. I will then provide two constructive proofs of universality for locally invariant cellular automata. The results provided in this talk can be found on arXiv:2102.06912.

  • 21 juin 2022 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Influence: a partizan scoring game on graphs’‘
    by Éric Rémila (GATE LSE)
    See abstract

    We introduce the game influence, a scoring combinatorial game, played on a directed graph where each vertex is either colored black or white. The two players, Black and White, play alternately by taking a vertex of their color and all its successors (for Black) or all its predecessors (for White). The score of each player is the number of vertices he has taken. We prove that influence is a nonzugzwang game, meaning that no player has interest to pass at any step of the game, and thus belongs to Milnor’s universe. We study this game in the particular class of paths where black and white vertices are alternated. We give an almost tight strategy for both players when there is one path. More precisely, we prove that the first player always gets a strictly better score than the second one, but that the difference between the scores is bounded by 5. Finally, we exhibit some graphs for which the initial proportion of vertices of the color of a player is as small as possible but where this player can get almost all the vertices.

  • 31 mai 2022 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Quantum Entanglement and Quantum Cellular Automaton’‘
    by Kevissen Sellapillay (PhD LIS & CPT)
    See abstract

    Entanglement is a quantum property with no classical counterpart. We briefly review entanglement, its definition and quantities to measure it. We then present a perturbation of a quantum cellular automaton based on rule 201 and study its entanglement propagation properties. This quantum cellular automaton breaks the Hilbert space into different ergodic sectors.

  • 5 avril 2022 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘A Pipeline for Solving Equations over Discrete Dynamical Systems’‘
    by Sara Riva (PhD I3S, Sophia Antipolis)
    See abstract

    Finite Discrete Dynamical Systems (DDS) are a formal model to study complex phenomena appearing in many different domains. Hypotheses on the fine structure of the system can be modeled via polynomial equations over DDS. For example, AX=B represents the hypothesis that the dynamics of B is given by the joint action of a known system A and an unknown one X. Finding X would validate the hypothesis; the hypothesis is invalid if no solution exists. In general, solving generic equations over DDS has been proved undecidable. In the hypothesis validation case, a possible approach is to study the solutions through a finite number of different abstractions of the problem. Each abstraction allows studying specific properties and parts of specific dynamics. We focus on hypotheses about the cardinality of the set of states, the cyclic behaviour and the transient behaviour of DDS. We introduce a complete pipeline based on Multi-valued decision diagrams to validate hypotheses on the cardinality of the set of states and on the asymptotic behaviour, contained in the cyclic parts, of a DDS. These results are a step forward in the analysis of complex dynamics graphs as those appearing, for instance, in biological regulatory networks or in systems biology. Furthermore, this approach opens up new research challenges in the field of ordered decision diagrams and their operations.

  • 8 mars 2022 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Théorème du point fixe de Kleene en calculabilité’‘
    by Kévin Perrot (LIS)
    See abstract

    Pour toute transformation de programme h calculable, il existe un programme n tel que n et h(n) font la même chose. Ce théorème est génial, et sa preuve d’une simplicité déconcertante. De plus ses corollaires sont nombreux, comme l’indécidabilité de l’arrêt, et l’existence de quine (programme qui affiche en sortie son propre code) dans tout langage de programmation acceptable. On programmera un quine ensemble :-) Cet exposé est tiré d’une séance de l’UE Calculabilité Avancée en M1 Info, pas de résultat nouveau, juste un peu de culture.

  • 8 February 2022 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Purely local self-assembly algorithm for a quasiperiodic octagonal tiling’‘
    by Ilya Galanov
    See abstract

    Self-assembly is the process in which the components of a system, whether molecules, polymers, or macroscopic particles, are organized into ordered structures as a result of local interactions between the components themselves, without exterior guidance. This talk is devoted to the self-assembly of aperiodic tilings. Aperiodic tilings serve as a mathematical model for quasicrystals - crystals that do not have any translational symmetry. Because of the specific atomic arrangement of these crystals, the question of how they grow remains open. Simulations strongly support the evidence that the algorithm we developed grows aperiodic tilings up to an unavoidable but neglectable proportion of missing tiles. In this talk, we state the first theorem regarding the Golden-Octagonal tilings and formulate conjectures for future results.

  • 14 December 2021 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Plans discrets substitutifs’‘
    by Victor Lutfalla
    See abstract

    Je vais présenter mes travaux de thèse sur les Plans Discrets Substitutifs. Les plans discrets substitutifs sont une famille de pavages du plans.

    Les pavages du plan par des losanges unitaires avec un nombre fini n de directions d’arêtes peuvent être relevés dans R^n en fixant un sommet qui est envoyé sur l’origine et en associant à chaque direction d’arête un vecteur de la base canonique de R^n. Les pavages sont ainsi relevés en des surfaces discrètes de R^n. Un plan discret est un pavage dont le relevé dans R^n approxime un plan 2D de R^n.

    Les substitutions sont des applications qui à chaque tuile associent un motif de tuiles (comme pour les substitutions sur les mots), une substitution est ensuite étendue aux motifs en l’appliquant séparément à chaque tuile et en recollant ensuite les résultats, notez que le recollement des résultats est plus compliqué sur les pavages que sur les mots. Un pavage est dit substitutif s’il existe une substitution telle que tous les motifs finis du pavages peuvent être générés par cette substitution.

    Je vais présenter deux familles de pavages : Sub Rosa et Planar Rosa.Les pavages Sub Rosa sont des pavages substitutifs avec symétrie rotationnelle d’ordre 2n mais ils ne sont pas des plans discrets.Les pavages Planar Rosa sont des plans discrets substitutifs avec symétrie rotationnelle d’ordre 2n.

  • 7 December 2021 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Conjunctive grammars, cellular automata and logic’‘
    by Théo Grente
    Slides: PDF
    See abstract

    Conjunctive grammars are an extension of context free grammars with a conjunction operation. Their expressive power (even on a unary alphabet) is largely unknown. When restricting time, space or even communication, cellular automata (CA) can act as languages recognizer defining complexity classes. The goal of this talk is to prove the inclusion of conjunctive languages in one of CA complexity classes. The proof uses a programming method which relies on exact characterizations of interesting CA complexity classes by sub-logics of ESO (existential second-order logic) with Horn formulas as their first-order part. By using this method, we just have to define conjunctive grammars in our logic to obtain an inclusion result.

  • 23 November 2021 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Classes de transitivité pour les sous-décalage de type fini multi-dimensionnels’‘
    by Silvère Gangloff
    Slides: PDF
    See abstract

    Ce travail est en commun avec B.Hellouin et P.Oprocha. Les sous-décalages de type fini multidimensionnels ont été étudiés dans les dernières décennies à travers le spectre de propriétés topologiques telles que la transitivité ou le mélange. Dans des travaux récents, nous avons montré, avec B.Hellouin et M.Sablik, qu’en quantifiant ces propriétés, il est possible de caractériser la complexité de ces systèmes dynamique en fonction de la quantité de transitivité/mélange (en particulier du point de vue calculabilité). Cependant les différentes classes de transitivité (relatives à cette quantification) sont mal comprises dans le cas général. Avec B.Hellouin et P.Oprocha, nous travaillons à caractériser ces classes dans le cadre restreint des Hom shifts, c’est à dire les sous-décalages définis par des ensembles de motifs interdits consistant en des dominos dont les symboles ne sont pas voisins dans un graphe fini non-orienté. Dans cet exposé, je présenterai le problème, ainsi que des résultats obtenus et attendus dans cette direction, qui laissent espérer une caractérisation complète des classes de transitivité dans le cas des Hom shifts.

  • 16 November 2021 : 14h00 at Visio
    ‘‘Spatial search by continuous-time quantum walk’‘
    by Leonardo Novo
    Video: see on AMUpod
    See abstract

    I will present two recent contributions about the performance of quantum search algorithms based on continuous-time quantum walks [1,2]. First, I will present some general results about the performance of the algorithm introduced by Childs and Goldstone [Phys. Rev. A 70, 022314 (2004)], which uses a continuous-time quantum walk to find a marked node on a graph of n nodes. This algorithm is said to be optimal if it can find any of the nodes in the graph in O(sqrt(n)) time. I will present conditions, based on the spectrum of the Hamiltonian driving the quantum walk, that can be used to predict whether the algorithm is optimal on a given graph. In the second part of the talk, I will present a new algorithm based on Hamiltonian evolution that finds marked nodes on any ergodic reversible Markov chain P quadratically faster than its classical hitting time. This algorithm can be seen as a quantum walk on the edges of a Markov chain and its performance matches that of discrete-time quantum walk search algorithms based on the Szegedy formalism. This work improves upon the recent work of [Phys. Rev. A 102, 022227 (2020)] and finally closes a theoretical gap between the performance of continuous-time and discrete-time quantum walk approaches for search.

    References:
    - On the optimality of spatial search by continuous-time quantum walk, Shantanav Chakraborty, Leonardo Novo, and Jérémie Roland, Phys. Rev. A 102, 032214 (2020)
    - Finding a marked node on any graph by continuous-time quantum walk , Shantanav Chakraborty, Leonardo Novo, and Jérémie Roland, Phys. Rev. A 102, 022227 (2020)

  • 4 November 2021 : 15h00 at Visio
    ‘‘Majority-3SAT (and Related Problems) in Polynomial Time’‘
    by Shyan Shaer Akmal
    Video: see on AMUpod
    See abstract

    Majority-SAT is the problem of determining whether an input n-variable formula in conjunctive normal form (CNF) has at least 2^{n-1} satisfying assignments. Majority-SAT and related problems have been studied extensively in various AI communities interested in the complexity of probabilistic planning and inference. Although Majority-SAT has been known to be PP-complete for over 40 years, the complexity of a natural variant has remained open: Majority-kSAT, where the input CNF formula is restricted to have clause width at most k. It recent work, joint with Ryan Williams, we prove that for every k, Majority-kSAT is in P. In fact, for any positive integer k and rational ρ∈(0,1) with bounded denominator, we present an algorithm which determines whether a given k-CNF has at least ρ2^{n} satisfying assignments, in deterministic linear time (whereas the previous best-known algorithm ran in exponential time). In this talk we give an overview of the main ideas behind these algorithms, and highlight the implications for some additional problems related to counting satisfying assignments.

  • 2 November 2021 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘ZX-calculus, a Swiss army katana for quantum computing’‘
    by Titouan Carette
    Slides: PDF
    See abstract

    It usually requires months to master the concepts of quantum mechanics necessary to quantum computing. This time can be reduced drastically by using conveniently designed notations. The ZX-calculus, a graphical language to denote tensor, have been claimed to be such a powerful tool allowing to learn and then reason efficiently on quantum processes. I will support this claim by providing several examples of applications through three extensions of the ZX-calculus that have been introduced in the recent years, namely: mixed states, scalable, and stream ZX-calculus.

  • 5 October 2021 : 14h00 at Visio and TPR2/04.05 (Luminy)
    ‘‘Quantum Natural Language Processing’‘
    by Giovanni De Felice
    See abstract

    I will talk about string diagrams, how they are used to capture different models of quantum computation (e.g. circuit-based, measurement-based and linear optical quantum computing), as well as different models of natural language syntax (e.g. context-free grammars, pregroup grammars). I will show how to use this to perform natural language processing on currently available quantum hardware.

  • 16 February 2021 : 14h00 at Visio and TPR2/04.02 (Luminy)
    ‘‘Classical and quantum causal graph dynamics’‘
    by Amélia Durbec
    See abstract

    Causal graph dynamics are a twofold extension of cellular automata : the underlying grid is extended to an arbitrary bounded-degree graph and the graph itself is allowed to evolve over time. Such dynamics are insightful toy models for theoritical physics in both the reversible and the quantum regime. In this talk, we are going to see how a graph dynamics can be reversible and yet create/destroy vertices, and that vertex names are necessary in order to prevent faster-than-light signalling. We will finish this talk with outlooks towards graph self-assembly and graph subshifts.

  • 5 January 2021 : 14h00 at Visio
    ‘‘Simulation entre modèles de calcul naturel et modularité des réseaux d’automates’‘
    by Pacôme Perrotin
    See abstract

    Nous explorons différentes généralisations concernant les modèles de calcul naturel. La plus théorique est la notion de simulation entre modèles, pour laquelle nous décrivons une série de propositions de définition, en discutant des intérêts et des failles de chacune d’elles. Nous profitons des définitions les plus prometteuses pour élargir le propos sur les possibles conséquences de la simulation en théorie de la complexité, comme la construction de nouvelles classes de complexité en proposant la substitution de la réduction polynomiale par la simulation. Notre approche plus appliquée consiste en la généralisation des réseaux d’automates sous formes de modules, qui possèdent des entrées. Ce formalisme permet d’approcher les questions de la dynamique des réseaux d’interactions sous un nouvel angle : nous explorons son utilité en tant qu’outil modulaire propre à simuler de façon flexible de nombreux objets similaires, ainsi que l’expressivité des modules acycliques. Ceux-ci permettent la caractérisation de la dynamique des réseaux d’automates sous la forme de fonctions de sortie. Cette expressivité nous autorise la description d’un processus d’optimisation de réseaux d’automates, qui réduit certains réseaux en taille tout en conservant des attracteurs équivalents.

  • 27 October 2020 : 14h00 at Visio
    ‘‘Rice-like theorems for automata networks’‘
    by Guilhem Gamard
    See abstract

    An automata network (AN for short) is a finite digraph where each node holds a state, choosen among a finite set, that evolves in function of the states of its inbound neighbors. Time is discrete and all nodes evolve synchronously and in parallel, similarly to what happens in an cellular automaton. In other terms, the differences between a cellular automaton and an automata network is that the “grid” is an arbitrary finite digraph, and that different nodes may have different update functions. ANs have been used to model neural networks, dynamics of expression and inhibition of genes, distributed algorithms, and more. Although ANs look like a model of computation, they are not Turing-complete, for they lack unbounded memory. Still, they are subject to some kind of “Rice theorems”, i.e., results along the lines of: “any nontrivial property of the function computed by an automata network is computationally hard to test”. In this talk, we will review several results that fit this pattern, as well as pieces of proof that hopefully may be reused in other contexts.

  • 6 October 2020 : 14h00 at Visio
    ‘‘The semiring of dynamical systems’‘
    by Antonio E. Porreca
    Slides: PDF
    Video: see on AMUpod
    See abstract

    We introduce an algebraic approach for the analysis and composition of finite, discrete-time dynamical systems in terms of the category-theoretical operations of sum (disjoint union) and (tensor) product, which correspond to alternative and synchronous execution. This defines a semiring structure over the set of dynamical systems (modulo isomorphism), which allows us to express decomposition problems in terms of factorisation and polynomial equations. We analyse the algebraic properties of the semiring and prove that most dynamical systems are irreducible, and that the reducible ones sometimes admit multiple factorisation into irreducibles. We also prove that polynomial equations over this semiring are, in general, algorithmically unsolvable, and that many solvable subclasses of equations, including linear ones, are intractable even if the explicit dynamics of the systems is given as input (while in applications, where the dynamical systems are described more succinctly, these problems are conjecturally even harder). Finally, we also analyse dynamical systems in terms of their “topographic profiles”, a more abstract view in terms of the number of states at a given distance from the limit cycles of the system, which turns out to share many of the same algebraic properties.

  • 14 April 2020 : 14h00 at Visio
    ‘‘Molecular computers in artificial chemistry’‘
    by Marius Buliga
    See abstract

    Download PDF

  • 18 February 2020 : 13h30 at Salle de réunion LIS-BU1 (Luminy)
    ‘‘Preuve du paradoxe de Banach-Tarski’‘
    by Kévin Perrot

  • 7 January 2020 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Simple Intrinsic Simulation of Cellular Automata in Oritatami Molecular Folding Model’‘
    by Nicolas Schabanel
    See abstract

    The Oritatami model was introduced by Geary et al (2016) to study the computational potential of RNA cotranscriptional folding as first shown in wet-lab experiments by Geary et al (Science 2014). In Oritatami model, a molecule grows component by component (named beads) into the triangular and folds as it grows. More precisely, the $\delta$ last nascent beads are free to move and adopt the positions that maximizes the number of bonds with the current structure. This dynamics captures the essence of cotranscriptional folding to a considerable extent, where an RNA sequence folds upon itself into complex shapes and functions while being synthesized (transcribed) out of its template DNA sequence.

    The Oritatami model was proven that it is capable of efficient Turing universal computation by Geary et al (2018) thanks to a quite complicated construction that simulates Turing machines via tag systems. We propose here a simple Oritatami system which intrinsically simulates arbitrary 1D cellular automata. Being intrinsic, our simulation emulates the behavior of the cellular automata in a readable way and in time linear in space and time of the simulated automaton. Furthermore, the number of bead types needed is quite modest (182 as opposed to 542), and the delay $\delta$ is 2 (instead of 3). The length of the transcript is also only quadratic in the size of the cellular automata: $O(rQ^{2(2r+1)}\log Q)$ for a cellular automata with $Q$ states and radius $r$ (whose size is thus $O(Q^{2r+1}\log Q)$). Our construction relies on the development of new tools which are simple enough that we believe that some simplification of them may be implemented in the wet lab. Our construction has been implemented and will be soon freely downloaded for testing.

  • 4 December 2019 : 10h30 at Salle de réunion du modulaire (Luminy)
    ‘‘Algebra, Tilings and Nivat’‘
    by Etienne Moutot
    See abstract

    A quel point peut-on créer des structures complexes à l’aide de motifs élémentaires ?

    La conjecture de Nivat dit que toute configuration (coloration de la grille Z^2) defaible complexité (le nombre de motifs qui y apparaissent est “faible”)est nécessairement périodique. Autrement dit, il est impossible des créer des configuration “complexes” (non périodiques) à l’aide d’un petit nombre de motifs de base.En 2015, Michal Szabados et Jarkko Kari ont publié leur premier article utilisant une approche algébrique pour s’attaquer à cette conjecture. Leur idée est de représenter une configuration comme une série formelle, et en étudiant certaines structures qui lui sont liées (tels que des idéaux polynomiaux bien choisis). Ce faisant, ils parviennent à exploiter plusieurs théorèmes d’algèbre pour s’approcher de la conjecture de Nivat sous des angles nouveaux.

    Dans cet exposé, je présenterai les travaux que j’ai effectué avec Jarkko Kari dans le continuation de la thèse de Michal Szabados. Je parlerais de nouveaux théorèmes utilisant ces outils algébriques pour se rapprocher encore une fois de la conjecture de Nivat. Nous avons notamment prouvé que la conjecture de Nivat est vraie pour les configurations uniformément récurrentes (dont tous les motifs peuvent se trouver “partout” dans la configuration).Une des conséquences de ce résultat est que le problème du domino est décidable pour les sous-shifts de faible complexité. Ce problème est indécidable de manière générale, et si la conjecture de Nivat est vraie, il serait décidable de manière évidente. Un des intérêt de notre résultat est qu’il permet de prouver cette décidabilité, sans pour autant avoir besoin de la conjecture de Nivat, seulement une version affaiblie.

  • 29 October 2019 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Quasériodes des mots biinfinis’‘
    by Guilhem Gamard
    See abstract

    Un mot fini q est une quasipériode d’un mot infini w si et seulement si w est recouvert de copies de q, éventuellement chevauchantes. Si w admet au moins une quasipériode, on dit qu’il est quasipériodique. Cette notion est apparue dans les années 1990 dans un contexte d’algorithmique du texte, puis fut employée en combinatoire des mots, ainsi que dans l’étude des subshifts.
    Un article récent (2016) donne une technique générale permettant de déterminer l’ensemble des quasipériodes d’un mot infini donné. Cette technique permet par exemple de caractériser les quasipériodes des mots sturmiens. En outre, elle permet de démontrer que les mots sturmiens standard sont les mots apériodiques possédant “le plus de quasipériodes possibles”. La première partie de cet exposé présentera ces résultats.
    Malheureusement, tous ces résultats ne portent que sur les mots infinis à droite ; dans le cas des mots biinfinis, la combinatoire du problème est considérablement plus compliquée. Le cas biinfini est cependant plus naturel pour la dynamique symbolique, car le shift d’un mot biinfini quasipériodique est encore quasipériodique (ce qui n’est pas vrai sur les mots infinis à droite). Dans la deuxième partie de cet exposé, nous verrons comment généraliser les résultats précédents au cas biinfini.

  • 11 July 2019 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Invariance de jauge dans les automates cellulaires’‘
    by Nathanael Eon
    See abstract

    L’invariance de jauge est une symétrie fondamentale en physique, permettant la dérivation des quatre interactions fondamentales (électromagnétique, faible, forte, gravitationnelle). D’autre part, les automates cellulaires sont largement reconnus comme un modèle de calcul naturel utile à la modélisation de phénomènes physiques. Cet exposé à pour but de montrer comment ces deux théories peuvent être réunies et les perspectives que l’on peut en tirer. L’exposé présentera les résultats obtenus pendant mon alternance ainsi que mon stage de M2. Gauge-invariance is an essential symmetry in Physics as it allows for the derivation of the four fundamental interactions (namely electromagnetic, weak, strong and gravitation). From a different perspective, cellular automata are a model of natural calculus largely known for its capacity to model physical phenomena. This talks aims at uniting those two theories and see what perspectives comes from such unification. The results presented comes from a research project which encapsulate my M2 internship.

  • 9 July 2019 : 13h30 at Salle de réunion du modulaire (Luminy)
    ‘‘Computational complexity of finite asynchronous cellular automata’‘
    by Enrico Formenti
    See abstract

    Cellular Automata (CA) are a well-established bio-inspired model of computation that has been successfully applied in several domains. In the recent years the importance of modelling real systems more accurately has sparkled a new interest in the study of asynchronous CA (ACA). When using an ACA for modelling real systems, it is important to determine the fidelity of the model, in particular with regards to the existence (or absence) of certain dynamical behaviors. This paper is concerned with two big classes of problems: reachability and preimage existence. For each class, both an existential and a universal version are considered. The following results are proved. Reachability is PSPACE-complete, its resource bounded version is NP-complete (existential form) or coNP-complete (universal form). The preimage problem is dimension sensitive in the sense that it is NL-complete (both existential and universal form) for one-dimensional ACA while it is NP-complete (existential version) or PI^P_2-complete (universal version) for higher dimension. (article/pii/S0304397515011421)

  • 2 July 2019 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Étude d’un exemple de dynamique causale de graphe quantique’‘
    by Alan Gardin
    See abstract

    La présentation concerne l’étude d’une dynamique causale de graphe quantique. Il existe des résultats théoriques sur le sujet, que j’espère éclairer en présentant un exemple d’une telle dynamique. J’expliquerai notamment comment ce modèle a été construit, et quels ont été les problèmes rencontrés. Une fois cet exemple défini, je m’intéresserai aux applications potentielles de ce modèle, et plus particulièrement aux capacités de calcul. Enfin, j’aborde l’étude théorique de ce modèle d’un point de vue mathématique. Cette approche permettra éventuellement à terme de déduire certaines propriétés utiles à l’étude des capacités de calculs du modèle.

  • 4 June 2019 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Machines de Turing à temps infini : des fondements aux applications’‘
    by Sabrina Ouazzani
    See abstract

    Dans cet exposé je vous présenterai les fondements des machines de Turing à temps infini, en particulier comment calculer avec et quelques unes de leurs particularités issues de mes travaux de recherche, mais j’en présenterai aussi de nouvelles applications, notamment en analyse, sur lesquelles je travaille actuellement avec Olivier Bournez. En particulier, quels liens ces machines entretiennent-elles avec les équations différentielles ? Je conclurai en introduisant quelques questions d’ouverture.

  • 23 May 2019 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Solving Equations on Discrete Dynamical Systems’‘
    by Sara Riva
    See abstract

    Boolean automata networks, genetic regulation networks, and metabolic networks are just a few examples of biological modeling by discrete dynamical systems (DDS). A major issue in modeling is the verification of the model against the experimental data or inducing the model under uncertainties in the data. Equipping finite discrete dynamical systems with an algebraic structure of semiring provides a suitable context for hypothesis verification on the dynamics of DDS. Indeed, hypothesis on the systems can be translated into polynomial equations over DDS. Solutions to these equations provide the validation to the initial hypothesis. Unfortunately, finding solutions to general equations over DDS is undecidable. However, many tractable cases have been highlighted. In this article, we want to push the envelop further by proposing a practical approach for such cases. We demonstrate that for many tractable equations all goes down to a “simpler” equation. However for us, the problem is not to decide if the simple equation has a solution, but to enumerate all the solutions in order to provide an insight on the set of solutions of the original, undecidable, equations. We evaluate experimentally our approach and show that it has good scalability property.

  • 21 May 2019 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Designing devices with Variational Quantum Circuits’‘
    by Filippo Miatto
    See abstract

    The design of realistic quantum devices can be extremely challenging, due to the complexity of quantum interactions or to the scarcity of analytical methods in certain areas, such as non-gaussian optical interactions. My approach is to start from a network of random quantum interactions and then optimize their parameters until we obtain the desired device. This is possible with a Variational Quantum Circuit (VQC), which allows for gradient descent methods as the optimization workhorse. The advantage of this method is that the raw VQC can be composed of realistic devices and designed for full generality, which means that a) a solution consists in the explicit blueprint with all the correct parts, their connectivity and their parameters all sorted out and b) it can be applied to a variety of domains, not just quantum optical devices. I apply this method to the design of a realistic one-way quantum repeater, which includes non-gaussian quantum optical interactions and is therefore a very difficult problem to solve without clever numerical methods. A preliminary result shows that it is in principle possible to have a repeater interaction with at most a few hundred elementary optical elements, which is an extremely promising result. Our current goal is to combine our method with Reinforcement Learning techniques to design better and better raw VQCs that can achieve the same performance with fewer elements and ultimately lead to the simplest and cheapest versions of the devices that we look for.

  • 14 May 2019 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘A new logic for quantum computing’‘
    by Dominic Horsman
    See abstract

    In this talk I will give an introduction to the use of the ZX calculus of observables as a new language in which to frame quantum computing. In particular, I will focus on how it acts as a high-level design and compilation language for surface codes with lattice surgery. ZX calculus diagrams allow purely diagrammatic equational reasoning, and I will show how they are especially suited to representing the structures of surface codes. Looking particularly at the operations of lattice surgery, I show how the generators of the calculus form a direct model for splitting and merging operations. This has important implications for how we think about quantum information processing, and I will discuss a few such issues here.

  • 6 May 2019 : 14h30 at Salle G.02.12 du TPR1 (Luminy)
    ‘‘Inference and of elementary cellular automata limit-graphs’‘
    by Eurico Ruivo
    See abstract

    Cellular automata are locally defined dynamical systems which are discrete in space, time and in the state variables, and capable of presenting arbitrarily complex global emergent behaviour. One core question in the study of cellular automata refers to their limit behaviour, that is, to the global dynamical features in a infinite time evolution. For finite time evolutions, one-dimensional cellular automata present dynamics which can be described by regular languages and, therefore, by finite automata. Also, there are growth patterns in the evolution of such finite automata for some cellular automata rules. In this work we present the formalisation of an automatic method to compute such structures. Based on this, the rules of the elementary cellular automata rule space were classified according to the existence of a growth pattern in their finite automata and a method to infer the limit graph of some elementary cellular automata rules by analysing the regular expressions describing their behaviour in finite-time is presented.

  • 30 avril 2019 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘The search for a complexity notion for organised dynamical systems’‘
    by Silvère Gangloff
    See abstract

    The neuroscientists G. Tononi, O.Sporns and G.M. Edelman proposed in 1994 a notion of complexity, that they called neural complexity, which aims at measuring the balance in a system between independance or specialisation of its parts and their integration into the whole that have organised systems such as the brain. This work has attracted recently the attention of mathematicians: in 2009, J. Buzzi and L. Zambotti defined a class of functionals called intricacies, which includes the particular case of neural complexity, and studied the maximisers of these functionals. This notion of intricacy was studied by K. Petersen and B. Wilson (2016) in the frame of symbolic dynamics, and computed a formula for some intricacy for very elementary one-dimensional subshifts of finite type. In this talk, I will expose the basic material to understand this problem and make an overview of the literature. In the end, I will try to expose some directions for research on this subject.

  • 2 avril 2019 : 15h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Could density determination be solved with one-dimensional binary cellular automata with asynchronous update?’‘
    by Pedro Balbi de Oliveira
    See abstract

    This title reflects the question that will start to be addressed during my visit to LIS. In the talk I will discuss the background about it, and give some idea about how the problem can be tackled. In its original formulation, density determination refers to the problem of deciding, by means of a one-dimensional cellular automaton rule, which is the most frequent bit in a cyclic binary configuration. This is one of the most widely studied benchmark decision problems in the cellular automata literature. In spite of various positive and negative results already known on the problem, in its various formulations, the possibility of solving it with a rule being updated in a deterministic asynchronous fashion is still open.

  • 19 février 2019 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘An introduction to rule algebras and stochastic mechanics for theories of rewriting’‘
    by Nicolas Behr
    See abstract

    Reference: https://arxiv.org/abs/1807.00785
    In this talk, without assuming any particular familiarity of the audience with the relevant theory of (M-) adhesive categories, I will provide an introduction to the so-called Double-Pushout (DPO) rewriting framework. Particular emphasis will be given to a novel series of results that concerns a certain form of associativity of the notion of sequential compositions of rewriting rules. In fact, it is this associativity that (via the mathematical framework of rule algebras) permits to make contact between classical notions of manipulations of graphs in combinatorics and statistical physics on the one hand, and the category-theoretical formulation of rewriting theories on the other hand. Some explicit application examples in the field of continuous-time Markov chains based on stochastic DPO-rewriting systems will be presented, including models of dynamical random graph ensembles (such as e.g. a birth-death process on edges of finite graphs).

  • 29 janvier 2019 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Analogies between subshifts and groups: Higman type theorems for subshifts’‘
    by Pascal Vanier
    See abstract

    Subshifts are sets of colorings of Z² by a finite alphabet that avoid some family of forbidden patterns. We investigate here some analogies with group theory that were first noticed by Emmanuel Jeandel. In particular we will show theorems on subshifts inspired by Higman’s embedding theorems of group theory, among which, the fact that subshifts with a computable language can be obtained as restrictions of minimal subshifts of finite type. This is joint work with Emmanuel Jeandel.

  • 22 janvier 2019 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Sur les délais de communication entre systèmes numériques (microcontrôleurs)’‘
    by Cédric Berenger
    See abstract

    Lors de mon stage de recherche, j’avais développé un algorithme de synchronisation pour de grands réseaux sur la base d’un modèle probabiliste de délais de transmission d’un noeud à l’autre. Lors d’essais avec des systèmes réels, nous sommes tombés sur des observations inattendues qui nous obligent de repenser les modèles, mais qui ouvrent aussi des perspectives d’applications très surprenantes en transformant un défaut en un atout.

  • 20 décembre 2018 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘SAT est NP-complet, la preuve !’‘
    by Kévin Perrot
    See abstract

    Ne croyez pas ce que l’on vous a dit, le théorème de Cook-Levin n’est pas si difficile que cela à démontrer… J’ai longtemps admis cette preuve, et après l’avoir lue dans le livre de Sylvain Perifel, j’ai envie de la partager ! Venez ajouter LA brique de base à vos connaissances en complexité, ou simplement réviser :-)

  • 15 novembre 2018 : 10h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Adiabatic methods in quantum control’‘
    by Francesca Chittaro
    See abstract

    Quantum control is the branch of control theory concerned with quantum systems, that is, dynamical systems at atomic scales, that evolve according to the laws of quantum mechanics.

    One fundamental issue in quantum control theory is the controllability of quantum systems, that is, whether is it possible to drive a quantum system to a desired state, by means of suitably designed control fields. To cover most theoretical and practical situations, several notion of controllability have been proposed, as, for instance, controllability in the evolution operator, pure state controllability, controllability in population and eigenstate controllability. After a brief introduction on the topic, I will expose some results on the approximate spread controllability of (closed) quantum systems, obtained by means of adiabatic techniques, and taking advantage of the presence of conical intersections between the energy eigenstates. These results have been published in [1],[2].

    Adiabatic techniques can be successfully used also to study the dynamics of open quantum systems. In particular, in [3] they have been applied to find an effective description of the evolution of open, weakly coupled quantum systems, where the sub-system of interest dissipate with much slower time scales than the rest of the system.

    [1] U. Boscain, F. C. Chittaro, P. Mason, M. Sigalotti Quantum Control via Adiabatic Theory and intersection of eigenvalues IEEE-TAC, (2012) 57, No. 8, 1970–1983
    [2] F. C. Chittaro, P. Mason Approximate controllability via adiabatic techniques for the three-inputs controlled Schrödinger equation, SIAM J. Control Optim., (2017), 55(6), 4202–4226.

  • 13 novembre 2018 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Exploring attractor invariance in elementary cellular automata’‘
    by Stephanie McLean
    See abstract

    We are interested in the study of the set of attractors of all 256 Elementary Cellular Automata (ECA) , i.e., one-dimensional, binary 3-neighbourhood cellular automata, dened on an n-cell lattice (n is the length of the automaton).

    Recent works have studied the invariance of their attractors against dierent update schemes, and how these aect their dynamics. Specically, in [1] was introduced the notion of k-invariance: an ECA rule r is k-invariant if its set of attractors, denoted by Fr(s), remains invariant for all update schemes s having blocks of length at most k (notice that k=1 stands for sequential update schemes, while k = n is the parallel, or synchronous one). In this context, the 1-invariance was studied in [2], where 104 ECA rules showed to have this kind of invariance. In [1] and [3] the authors studied the k-invariance, for 2 < k ≤ n, for all 104 ECA rules above mentioned.

    In this work, we explore another notion of attractor invariance “in between ECA rules”, we say that two ECA rules u and v are attractor equivalent over a set of update schemes S, if given any s in S, Fu(s) = Fv(s). We begin our study with the 1-invariant rules, searching for equivalences between their sets of attractors, for all 4 ≤ n ≤ 14, so as to have a set of rules that are “candidates” to be attractor equivalent, since we know that if u and v are both 1-invariant ECA rules, then their sets of attractors remain invariant, but not necessarily the same, for all sequential update schemes s. Attractor equivalence gives us new insights of the dynamical behaviour of a rule (and its equivalent rules) under dierent update schemes.

  • 23 octobre 2018 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘On the Complexity of the Stability Problem of Binary Freezing Totalistic (Asynchronous) Cellular Automata’‘
    by Diego Maldonado
    See abstract

    We study the computational complexity of a family of simple two-dimensional, two-state freezing CA under synchronous and asynchronous update scheme. In such family of CA, sites in state 0 change to state 1 depending only on the sum of the states of their neighbors, while sites in state 1 remain always in that state. The complexity of a CA is an automata is that of stability problem: it consists in the long-term prediction of the state of a site. We show that in this family of 32 local rules, is possible to find cases with P-Complete, NC, and constant time complexity.

  • 16 octobre 2018 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Automates cellulaires et solitons’‘
    by Guillaume Theyssier
    See abstract

    Les automates cellulaires sont à la fois un modèle de calcul et une famille de systèmes dynamiques discrets. On peut se demander comment leur complexité computationnelle et leur complexité dynamique sont liées. Cet exposé propose de faire un petit pas dans ce questionnement en se basant sur une notion générale de soliton. Nous nous intéresserons aux automates cellulaires SANS soliton et à leur propriétés dynamiques. Nous verrons en particulier que l’absence de soliton caractérise la randomisation dans les automates abéliens et explorerons les liens avec les notions de pré-expansivité et de diffusion dans le cas général.

  • 21 septembre 2018 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Nombre de points fixes des réseaux booléen : Complexité algorithmique’‘
    by Florian Bridoux
    See abstract

    Dans cette présentation nous allons nous intéresser aux réseaux booléens (RB). Un RB de taille n peut être vu comme une fonction f: {0,1}^n -> {0,1}^n ou bien comme un produit de n fonctions f_1, f_2, …, f_n de {0,1}^n à {0,1}. Un problème classique est le calcul du nombre de points fixes, c’est-à-dire le nombre de configurations x dans {0,1}^n tel que f(x) = x. Un objet souvent utilisé (et qui justifie la terminologie de « réseaux ») quand on s’intéresse aux réseaux booléens est le graphe d’interaction. Il s’agit d’un graphe à n sommets numérotés de 1 à n tel qu’il y a un arc entre le sommet i et j ssi la valeur de f_j(x) dépendant de la i-eme composante de x pour un certain x (= le sommet i “a une influence” sur j). Chaque RB a son graphe d’interaction mais un même graphe d’interaction peut correspondre à de nombreux RBs. Nous allons noter F(G) l’ensemble des RBs correspondant à un certain graphe d’interaction G. Et nous allons nous intéresser à la question: “Étant donné G et un entier k, existe-t-il f dans F(G) qui a au moins/au plus k points fixes?” Nous allons voir que selon la nature de k et l’exacte question posée, le problème peut appartenir à différentes classe de complexité allant de P à NEXPTIME.

  • 11 septembre 2018 : 16h15 at Salle de réunion du modulaire (Luminy)
    ‘‘Quantum Computation with Indefinite Causal Order’‘
    by Fabio Costa
    See abstract

    In a quantum computer, a system undergoes a sequence of quantum transformations, which can solve certain problems more efficiently than any classical computer. However, the order in which the transformations take place is fixed. I will present an extension of this model, where an additional quantum system controls the order between transformations. This new possibility provides an advantage for computational and communication problems, above what is achievable by “ordinary” quantum computers. The formalism describing this new model of computation has further applications to the study of novel physical regimes, which combine quantum superpositions with general relativistic causal structure.

  • 10 juillet 2018 : 11h at Salle de réunion du modulaire (Luminy)
    ‘‘Elementary particle dynamics, return times and combinatorics’‘
    by Enrico Formenti
    See abstract

    In this talk we will explore simple particle dynamics and see how it can be studied using discrete dynamical systems. We will focus on return time, namely, the expected time after which a given particle will appear again at some fixed position. In particular, we will see how in the non-resting case, the movement of particles can be encoded into combinatorial questions about paths in a peculiar lattice.

  • 10 juillet 2018 : 11h at Salle de réunion du modulaire (Luminy)
    ‘‘Quantum Machine Learning’‘
    by Hachem Kadri
    See abstract

    Quantum Machine Learning is an emerging field of research, with fast growth. This research field is largely driven by the desire to develop artificial intelligence that uses quantum technologies to improve the speed and performance of learning algorithms. In this talk I will give a brief introduction to quantum machine learning and discuss current challenges in the field. I will pay special attention to quantum perceptron models and our recent work on entangled kernel machines, giving new insights into the interaction between Quantum Computing and Machine Learning.

  • 6 juin 2018 : 14h at Salle de réunion du modulaire (Luminy)
    ‘‘A gauge-invariant reversible cellular automaton’‘
    by Nathanaël Eon
    See abstract

    Gauge-invariance is a fundamental concept in physics—known to provide the mathematical justification for all four fundamental forces. In this paper, we provide discrete counterparts to the main gauge theoretical concepts, directly in terms of Cellular Automata. More precisely, we describe a step-by-step gauging procedure to enforce local symmetries upon a given Cellular Automaton. We apply it to a simple Reversible Cellular Automaton for concreteness. From a Computer Science perspective, discretized gauge theories may be applied to numerical analysis, quantum simulation, fault-tolerant (quantum) computation. From a mathematical perspective, discreteness provides a simple yet rigorous route straight to the core concepts.

  • 5 juin 2018 : 14h at Salle de réunion du modulaire (Luminy)
    ‘‘Folding shapes with oritatami systems’‘
    by Nicolas Schabanel
    See abstract

    so as to maximize the number of bonds formed, self-assemblying into a shape incrementally. The parameter $\delta$ is called the “delay” and is related to the transcription rate in nature.

    This article initiates the study of shape self-assembly using oritatami. A shape is a connected set of points in the triangular lattice. We first show that oritatami systems differ fundamentally from tile-assembly systems by exhibiting a family of infinite shapes that can be tile-assembled but cannot be folded by any OS. As it is NP-hard in general to determine whether there is an OS that folds into (self-assembles) a given finite shape, we explore the folding of upscaled versions of finite shapes. We show that any shape can be folded from a constant size seed, at any scale $n\geq 3$, by an OS with delay $1$. We also show that any shape can be folded at the smaller scale $2$ by an OS with “unbounded” delay. This leads us to investigate the influence of delay and to prove that there are shapes that can be folded (at scale $1$) with delay $\delta$ but not with delay $\delta’<\delta$, for all $\delta > 2$.

    These results serve as a foundation for the study of shape-building in this new model of self-assembly, and have the potential to provide better understanding of cotranscriptional folding in biology, as well as improved abilities of experimentalists to design artificial systems that self-assemble via this complex dynamical process.

  • 22 mai 2018 : 14h at Salle de réunion du modulaire (Luminy)
    ‘‘Quantum simulations via quantum walks over the honeycomb and triangular lattices’‘
    by Iván Márquez
    See abstract

    In this seminar we will talk about how to simulate quantum physical models via discrete-time quantum walks (DTQWs) over hexagonal and triangular lattices. We will define what a QW is from a computer science perspective. The study of QWs is growing due to two reasons. First, different kind of Quantum Computing algorithms have been created using them in an efficient way. On the other hand, they can be used for the purpose of quantum simulating in the future quantum simulation devices.

    From the quantum simulation perspective, QWs have been extensively used for reproducing relativistic particles dynamics described by the Dirac equation, always using regular lattices. We will show that QWs does not need to rely on the regular lattice grid, and that they can be casted on the hexagonal and triangular grid instead. We believe that this constitutes an important step towards: modeling propagation in crystalline materials; identifying substrates for QW implementations; studying topological phases and understanding propagation in discretized curved spacetime.

  • 17 mai 2018 : 14h at Salle des commissions, Bât TPR 2 - 1er étage (Luminy)
    ‘‘Classical and Quantum Simulations via Quantum algorithms’‘
    by Pedro Costa
    See abstract

    The era of quantum computers has already started. One important question that we can do now that we have these quantum devices ready is which quantum model of computation will be a good choice for encoding the huge number of quantum algorithms available. Another important question which is also extremely important to people that work in the industry that very often employs numerical methods to solve differential equations is that if these numerical methods are a promising application for quantum computers. Going to these directions we will present in this seminar our latest results where we introduce a partitioned model of quantum cellular automata and show how it can simulate, with the same amount of resources, various models of quantum walks. All the algorithms developed within quantum walk models are thus directly inherited by the quantum cellular automata. The latter, however, has its structure based on local interactions between qubits, and as such it can be more suitable for present (and future) experimental implementations. In the part related with numerical methods to solve differential equations, we will present a quantum algorithm for simulating the wave equation under Dirichlet and Neumann boundary conditions. The algorithm uses Hamiltonian simulation and quantum linear system algorithms as subroutines. Relative to classical algorithms for simulating the D-dimensional wave equation, our quantum algorithm achieves exponential space savings, and a speedup which is polynomial for fixed D and exponential in D. We also consider using Hamiltonian simulation for Klein-Gordon equations and Maxwell’s equations.

  • 15 mai 2018 : 14h at Salle de réunion du modulaire (Luminy)
    ‘‘Systèmes dynamiques finis, jeux des chapeaux et théorie des codes’‘
    by Hervé Seligmann
    See abstract

    Three mechanisms reveal unsuspected information in protein-coding genes: 1) alternative transcriptions that transform along systematic rules template sequences (for example systematic deletions of k nucleotides after each n transcribed nucleotides and systematic exchanges between nucleotides, such as AC or A>C>G>A); 2) codon expansion, where tRNAs with anticodons expanded by noncoding nucleotide(s) decode expanded codons; and 3) reassignments of codons to different amino acids. Here I present evidences for mechanisms 1 and 2, and associated self-correcting properties of the genetic code.

  • 15 mai 2018 : 11h at TPR2, salle 304-306 (Luminy)
    ‘‘Cryptic genes and genetic codes in mitochondria: Some of DNA’s unexplored coding dimensions’‘
    by Maximilien Gadouleau
    See abstract

    Un système dynamique fini (FDS) est un réseau d’entités qui interagissent au cours du temps. Chaque entité a un état parmi q possibles, pour q ≥ 2 donné, qui varie en fonction du temps et des états d’autres entités. Formellement, un FDS est une fonction f de {0,1,…,q-1}n dans lui-même (n étant le nombre d’entités) ; un FDS avec q=2 est ainsi un réseau booléen. L’un des problèmes majeurs de l’étude des FDS est d’étudier la dynamique du réseau en fonction de son graphe d’interaction, qui indique les relations d’influence parmi les entités. Ici nous nous intéressons à l’existence d’un FDS f stable, i tel que pour tout état x, son successeur f(x) a au moins une coordonnée égale à celle de x. Nous relions ce problème au jeu des chapeaux de Winkler et nous utilisons la théorie des codes pour construire des FDS stables avec des graphes d’interaction très particuliers et contre-intuititifs.

  • 10 avril 2018 : 14h at Salle des commissions, Bât TPR 2 - 1er étage (Luminy)
    ‘‘Quantum walks in curved spacetime’‘
    by Stefano Facchini
    See abstract

    A discrete-time Quantum Walk is essentially a unitary operator driving the evolution of a single particle on the lattice. We introduce the Grouped QWs, a generalization of the usual QWs where (i) the input is allowed a simple prior encoding and (ii) the local unitary coin is allowed to act on larger than usual neighborhoods; we show that it allows us to recover the Dirac equation in curved spacetime. Moreover we discretize the coin operator itself, only allowing a finite set of elementary local unitary operators. The discretization has the practical advantage of allowing easier experimental implementation, as well as of being of interest for studyingthe quantization of the metric.

  • 6 avril 2018 : 14h at Salle de réunion du modulaire (Luminy)
    ‘‘Entropy Inequalities, Secret Sharing and Applications’‘
    by Tarik Kaced
    See abstract

    Après une introduction au partage de secret, je présenterais quelques résultats sur le partage de secret non-parfait. Nous expliquerons la méthode des inégalités d’information pour obtenir des bornes sur l’efficacité des schémas de partage. Nous expliquerons des résultats généraux sur la géométrie du cône d’entropie et leurs applications.

  • 5 avril 2018 : 14h at Salle de réunion du modulaire (Luminy)
    ‘‘Communication topologies in natural computing’‘
    by Antonio Porreca
    See abstract

    When analysing the computational properties and the efficiency of uniform parallel computing models, most of these turn out to be either equivalent to deterministic Turing machines, thus characterising the complexity class P in polynomial time, or are otherwise capable of solving in polynomial time the problems that sequential computing devices solve in polynomial space (i.e., the complexity class PSPACE).

    However, certain natural computing models seem to escape this binary classification. In particular, several variants of parallel devices inspired by cell biology, called membrane systems, have been recently proved to characterise complexity classes between P and PSPACE when working in polynomial time. Some of these classes are rather unusual in the literature, and had previously only been defined in terms of Turing machines with oracles, rather than being characterised by a more concrete model of computation.

    Fundamental in the characterisation of these complexity classes is the communication topology of the device, that is, the graph along whose edges communication between the sequential computing units is allowed. The graph-theoretic (e.g., directedness, diameter) and geometric properties (e.g., embeddability in given metric spaces), as well as the description complexity of the graph (e.g., how the the adjacency list of a vertex can be computed) all influence the overall efficiency of the resulting device.

    In this talk we discuss the known relations between communication topology and computational complexity in membrane systems, and we propose to investigate these relations more generally and more abstractly by choosing a more convenient reference model, namely a variant of automata networks.

  • 3 avril 2018 : 16h at Salle de réunion du 3e étage de la FRUMAM (Saint-Charles).
    ‘‘Réseaux biologiques : algorithmique et optimisation’‘
    by Ricardo Andrade
    See abstract

    Dans cette présentation, je vais parler de deux problèmes d’énumération qui apparaissent lors de l’étude des réseaux biologiques. Le premier est le problème d’énumération d’ensembles de précurseurs dans un réseau métabolique. Un réseau métabolique est l’ensemble des processus chimiques et physiques qui déterminent le fonctionnement du métabolisme d’un organisme. Ce type de réseau est fréquemment modélisé comme un graphe de composés, un graphe biparti ou un hypergraphe, et un ensemble de précurseurs est un ensemble de composés source qui sont utilisés par un organisme pour produire un ensemble de composés cible. Le deuxième problème est une formulation bi-objective du problème du transversal minimum dans un hypergraphe. La motivation biologique est l’identification de gènes qui sont liés à des mutations qui contribuent directement au cancer. Notre hypergraphe modélise un réseau d’interaction de gènes. Les sommets correspondent à des gènes et il existe une arête entre deux gènes s’ils interagissent entre eux. Je vais présenter les problèmes et leurs motivations biologiques ainsi que brièvement quelques résultats de complexité et des algorithmes pour les résoudre.

  • 29 mars 2018 : 14h at Salle de réunion du 3e étage de la FRUMAM (Saint-Charles).
    ‘‘Utilisation de la programmation dynamique comme stratégie pour l’algorithme de simulation parfaite’‘
    by Christelle Rovetta
    See abstract

    En 1996, Propp et Wilson ont proposé un algorithme permettant l’échantillonnage sans biais de la distribution stationnaire d’une chaîne de Markov ergodique. Ce dernier appelé aussi algorithme de simulation parfaite, requiert la simulation en parallèle de tous les états possibles de la chaîne. Un des challenges lorsque l’on veut faire de l’échantillonnage par simulation parfaite réside généralement à mettre en place des stratégies permettant de ne pas avoir à simuler toutes les trajectoires.

    Un réseau fermé de files d’attente est un réseau dans lequel les clients ne peuvent ni entrer ni quitter le réseau. La dynamique de tels réseaux est couramment représentée par une chaîne de Markov ergodique. La difficulté pour qui voudrait appliquer l’algorithme de Propp et Wilson à de tels réseaux, réside dans la taille de l’espace des états qui est exponentielle en le nombre de files à laquelle s’ajoute une contrainte globale à savoir le nombre constant de clients.

    Pour commencer mon exposé, je présenterai une stratégie inspirée de la programmation dynamique qui permet la mise en œuvre de l’algorithme de Propp et Wilson pour des réseaux fermés de files d’attente. Dans un deuxième temps, je caractériserai la structure de données utilisée pour représenter l’espace des états, révélerai qu’elle englobe des objets combinatoires autres que les espaces d’états des réseaux fermés de files d’attente. Enfin, je terminerai par des applications induites par cette structure notamment dans le cadre de la méthode symbolique ainsi que dans le contexte de la cinétique du repliement d’ARN.

  • 22 mars 2018 : 14h at Salle de réunion du modulaire (Luminy)
    ‘‘Automaton groups, structure and properties’‘
    by Thibault Godin
    See abstract

    In this talk, I will give a brief overview of the interplay between the structure of a Mealy automaton and the properties of the (semi)group it generates.

    Mealy automata are special kind of transducers that can be used to generate (semi)groups. These (semi)groups have been widely used in mathematics since the 80’s as they can have some very interesting properties. For instance for first example of a group of intermediate growth has been discovered using a Mealy automaton. Furthermore, the underlying automata make these (semi-)groups amenable to computer science techniques, and I explain how automaton theoretic tools be used to predict characteristics of the group generated by a Mealy automaton.

  • 15 mars 2018 : 14h at Salle des commissions, Bât TPR 2 - 1er étage (Luminy)
    ‘‘Pavages, calculs et quasipériodicité’‘
    by Guilhem Gamard
    See abstract

    Une tuile de Wang est un carré unité dont les bords sont colorés. Si on dispose d’un ensemble fini de tuiles, on peut chercher à paver le plan : il s’agit de placer une copie d’une tuile dans chaque cellule de la grille unité, de telle façon que deux bords en contact ont toujours la même couleur. Les rotations et les symétries ne sont pas autorisées. Ce modèle permet de définir des «langages» sur les mots infinis en deux dimensions (autrement dit, des ensembles de colorations de ℤ²).

    On sait depuis les années 1960 qu’il est possible d’encoder n’importe quelle machine de Turing dans des tuiles de Wang, mais la construction est passablement complexe. Dans les années 1990, Jarkko Kari a donné un nouveau moyen d’encoder du calcul dans des tuiles de Wang. L’avantage de cette construction est que l’état du calcul à un temps T est stocké de façon «diluée» dans l’espace, si bien que le calcul peut continuer même en présence de petites «erreurs» locales.

    Nous montrerons, en utilisant des invariants de théorie de l’information, en quoi ces deux constructions sont fondamentalement différentes. Nous esquisserons ensuite une généralisation de la construction de Kari en un modèle de calcul sur les réels, résistant aux erreurs. Ce dernier point est l’objet de travaux en cours, il y aura donc plus de questions que de réponses au sujet de ce modèle de calcul.

    Dans une dernière partie, indépendante de ce qui précède, nous nous pencherons sur un cas particulier de règle locale définissable par tuiles de Wang : la quasipériodicité. Un mot fini (1D ou 2D) q est une quasipériode d’un mot infini w si ce dernier est recouvert d’occurrences de q, éventuellement chevauchantes. Nous verrons que la quasipériodicité possède un pouvoir expressif surprenamment important, et nous montrerons également comment la généraliser pour construire un modèle de calcul.

  • 15 mars 2018 : 11h at Salle des commissions, Bât TPR 2 - 1er étage (Luminy)
    ‘‘Tree sets: from combinatorics on words to symbolic dynamics’‘
    by Francesco Dolce
    See abstract

    A tree set is a language of finite words such that the extension graph of each of its elements, the graph describing left and right extensions of the word in the language, is a tree. This class of sets includes classical families such as Sturmian and episturmian sets, as well as the coding of interval exchange transformations.

    Despite the very simple combinatorial definition, this family of languages satisfies several non trivial properties. It also provides an interesting connection between combinatorics on words, symbolic dynamical systems, bifix codes and free groups.

    In this talk, we investigate these sets, focusing on some geometrical examples (interval exchanges and linear involutions) and on some closure properties.

  • 13 mars 2018 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Théorie des chemins et informatique : interactions’‘
    by Pierre-Louis Giscard
    See abstract

    Dans cet exposé nous démontrerons que les chemins sur les graphes obéissent à l’extension semi-commutative de la théorie des nombres ; complète avec ses éléments premiers, ses fonctions fondamentales (zêta, Möbius, von Mangoldt, Liouville …) et même une pléthore de relations entre objets combinatoires en extension directe de relations célèbres de la théorie des nombres. Cette approche fournie de nombreux outils nouveaux pour traiter des problèmes en mathématiques appliquées et informatique fondamentale. Nous présenterons un rapide tour d’horizon de ces applications, en combinatoire énumérative, calcul différentiel, inférence statistique, analyse des réseaux, algorithmique, apprentissage automatique sur les graphes, et dynamique quantique. Nous nous attacherons notamment à montrer comment des cribles non-commutatifs sur les chemins conduisent d’une part à une amélioration de prés de 25% sur le modèle de l’état de l’art concernant la prédiction des protéines de la plante Arabidopsis thaliana qui sont ciblées par des pathogènes; et d’autre part pour la détection de complexes de protéines chez la levure Saccharomyces cerevisiae. Nous illustrerons également les implications de nos résultats en sociologie, où un algorithme pour le dénombrement des cycles simples à permis de vérifier une vieille conjecture sur les interactions sociales; en chimie organique où nous classons des molécules selon leurs propriétés à l’aide d’un idempotent algébrique de Hopf; et pour la dynamique des ensembles de spins en résonance magnétique nucléaire.

    Mots clés : combinatoire des chemins; analyse des réseaux; apprentissage automatique; algorithmique.

    Références : le séminaire fera appel à de nombreuses publications, disponibles ici https://arxiv.org/find/all/1/all:+giscard/0/1/0/all/0/1.

  • 20 février 2018 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Méthodes de complétion et d’analyse de la dynamique des réseaux de régulation biologique : un résumé de mes travaux.’‘
    by Maxime Folschette (Dymec & Dyliss)
    See abstract

    Afin de contourner la complexité des systèmes d’équations différentielles, Kauffman (1969) puis Thomas (1973) jettent les bases d’une modélisation discrète sous forme de graphes, dont la dynamique est une restriction des réseaux d’automates, et assurant néanmoins une cohérence avec les systèmes réels modélisés. De nouvelles questions émergent alors, comme l’automatisation de la création de tels modèles discrets ou hybrides, ainsi que l’analyse de leur dynamique. Durant ce séminaire, après un rappel sur le classique modèle de Thomas, qui sert de base à mes travaux, j’exposerai les deux principaux aspects de ma recherche.
    * Le premier est la complétion de modèles, consistant à inférer la topologie ou les paramètres manquants d’un modèle.
    - Une première approche a consisté à utiliser une version modifiée de la logique de Hoare afin de trouver les valeurs de certains paramètres dynamiques ; pour cela, un comportement dynamique biologique tiré de la littérature est traduit en programme impératif et soumis à un calcul de plus faible précondition à la Dijkstra.
    - Une seconde approche, plus récente et expérimentale, consiste à reconstruire la topologie d’un réseau (les influences entre éléments, notamment) en se basant directement sur des données d’expression dans le temps, contrairement aux méthodes existantes qui requièrent une phase de discrétisation préalable.
    * Le second aspect est l’analyse de la dynamique d’un tel modèle complexe.
    - Analyse à l’aide d’Answer Set Programming (ASP), un paradigme de programmation logique récent et dont les solveurs donnent de bons résultats pour plusieurs problèmes classiques : atteignabilité d’un état, recherche des points fixes, recherche des attracteurs complexes.
    - Analyse à l’aide de µ-calcul, une extension de la logique temporelle classique CTL* : cela permet d’obtenir une plus grande expressivité, permettant notamment une recherche des attracteurs et des disruptions, ou encore une vérification de bisimulation entre modèles.
    - Analyse à l’aide d’analyse statique par interprétation abstraite : à l’inverse, pour une seule propriété donnée (ici, l’atteignabilité), réduit grandement la complexité et permet d’obtenir des résultats sur des grands modèles en très peu de temps.

  • 30 janvier 2018 : 9h30 at Salle du conseil, Bât TPR 2 - 1er étage (Luminy)
    ‘‘Continuous models of computation: computability, complexity, universality.’‘
    by Amaury Pouly (Max Planck Institute)
    See abstract

    In 1941, Claude Shannon introduced a continuous-time analog model of computation, namely the General Purpose Analog Computer (GPAC). The GPAC is a physically feasible model in the sense that it can be implemented in practice through the use of analog electronics or mechanical devices. It can be proved that the functions computed by a GPAC are precisely the solutions of a special class of differential equations where the right-hand side is a polynomial. Analog computers have since been replaced by digital counterpart. Nevertheless, one can wonder how the GPAC could be compared to Turing machines.

    A few years ago, it was shown that Turing-based paradigms and the GPAC have the same computational power. However, this result did not shed any light on what happens at a computational complexity level. In other words, analog computers do not make a difference about what can be computed; but maybe they could compute faster than a digital computer. A fundamental difficulty of continuous-time model is to define a proper notion of complexity. Indeed, a troubling problem is that many models exhibit the so-called Zeno’s phenomenon, also known as space-time contraction.

    In this talk, I will present results from my thesis that give several fundamental contributions to these questions. We show that the GPAC has the same computational power as the Turing machine, at the complexity level. We also provide as a side effect a purely analog, machine- independent characterization of P and Computable Analysis.

    I will present some recent work on the universality of polynomial differential equations. We show that when we impose no restrictions at all on the system, it is possible to build a fixed equation that is universal in the sense it can approximate arbitrarily well any continuous curve over R, simply by changing the initial condition of the system.

    If time allows, I will also mention some recent application of this work to show that chemical reaction networks are strongly Turing complete with the differential semantics.

  • 23 janvier 2018 : 10h00 at Salle du conseil, Bât TPR 2 - 1er étage (Luminy)
    ‘‘Crossing information on abelian sandpile models.’‘
    by Kévin Perrot
    See abstract

    We will study the family of abelian sandpile models :
    * on the two-dimensional grid,
    * with uniform neighborhood,
    and see how important is the shape of the neighborhood in the ability of the sandpile to simulate circuits, in order to prove the P-completeness of its prediction problem. The key point on which we will concentrate is the ability to construct a crossing gate. Joint work with Ha Nguyen, available at https://arxiv.org/abs/1709.00464.

  • 28 novembre 2017 : 14h30 at Salle des commissions, Bât TPR 2 - 1er étage (Luminy)
    ‘‘Edge-colored graphs representing pseudo-manifolds and discrete quantum gravity.’‘
    by Luca Lionni (LaBRI)
    See abstract

    (D+1)-Edge-colored graphs represent D-dimensional triangulations, and the geometrical properties of the latter are translated into graph roperties. This finds an application in discrete approaches to quantum gravity called dynamical riangulations. Triangulations should then be classified according to their mean urvature. We introduce a bijection with combinatorial maps, which often helps us solve this problem.

  • 28 novembre 2017 : 11h00 at Salle des commissions, Bât TPR 2 - 1er étage (Luminy)
    ‘‘Quantum cellular automata and quantum field theory.’‘
    by Terry Farrelly (Leibniz University, Hanover)
    See abstract

    The recent emergence of quantum computers as tools to simulate physics has been one of the driving forces of the field. Here we will look at a articular model of quantum computing called quantum cellular automata, which seems particularly seful for simulating quantum field theories. Many issues will arise, even for on-interacting quantum field theories, including finding the correct vacuum state on the lattice. e will discuss some of these problems, some results, and ideas for future work.

  • 27 novembre 2017 : 14h30 (séminaire LIRICA) at Salle de réunion du 2e étage de la FRUMAM (Saint-Charles)
    ‘‘Raisonnement non-monotone et prise de décision incertaine : application à un planeur autonome.’‘
    by Jose Luis Vilchis Medina
    See abstract

    L’exposé aborde l’étude d’un planeur autonome et de la prise de décision de pilotage, dans un environnement incertain. Dans ce cadre, le but d’un pilote de planeur est de rester en l’air le plus longtemps possible en prenant en compte des contraintes qui peuvent être contradictoires : contraintes de vol, recherche d’ascendance(thermal), réglementation aéronautique, sécurité … Dans un premier temps, nous allons essentiellement intéressés à modéliser le système capable de gérer des situations contradictoires et incertaines. Pour ce faire, nous allons utiliser un type de logique non-monotone, la logique des défauts de Reiter. Dans un deuxième temps, pour la prise de décision incertaine, nous allons définir une approche basée sur un critère non-probabiliste, pour choisir l’extension qui contient les actions optimales. Enfin, nous montrerons quelques résultats.

  • 3 octobre 2017 : 11h00 at Salle du conseil, Bât TPR 2 - 1er étage (Luminy)
    ‘‘Codes CSS et Complexes de chaines.’‘
    by Benjamin Audoux (I2M)
    See abstract

    Dans cet exposé, je rappellerais la définition des codes correcteurs d’erreurs quantiques dits CSS, et montrerai en quoi ils sont fortement liés à la notion, plus topologique, de complexe de chaine. Selon le temps disponible, je développerai ensuite quelques applications de ce point de vue topologique aux codes CSS.

  • 12 juillet 2017 : 10h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Algorithms for computing the rank of divisors on some classes of graphs.’‘
    by Ha Duong Phan (Institut de Mathématiques, Hanoi)
    See abstract

    The notion of rank of divisors on graphs was introduced by Baker and Norine in 2007 in showing the link with the similar notion on Riemann surfaces. Moreover, the authors have developed a theorem for divisors on graph analogue to the classical Riemann-Roch theorem. Since then, many works have studied for computing the rank of divisors on graphs. A very important is the new theorem on the NP-hardness complexity of the Problem of computing the rank of divisor on general graph. The proof of this result was based on the proof of the NP-hardness of the Problem of finding the minimum recurrent configurations of Chip Firing Game on directed graphs (by Perrot and Pham). In this talk, we will present some (polynomial) algorithms for computing the rank of divisors on some classes of graphs.

  • 20 juin 2017 : 14h30 at Salle de réunion du modulaire (Luminy)
    ‘‘Modélisation d’un système résilient en utilisant une logique non-monotone.’‘
    by Jose Luis Vilchis Medina
    See abstract

    Dans cet exposé, nous présentons un système résilient d’un moto-planeur autonome. Ce type de système a la caractéristique à s’adapter aux perturbations et/ou changement de consignes. Dans ce contexte, nous nous intéressons au pilotage autonome d’aéronefs. Ce type de problème est dit résilient puisque les perturbations “internes” (sécurité et sauvegarde de l’aéronef) et “externes” (changement de conditions atmosphériques) sont des informations capitales à partir desquelles le système doit réagir pour appliquer les actions nécessaires pour atteindre une zone de stabilité ou parvenir à compléter ses différents objectifs (par exemple une trajectoire de vol stable ou un atterrissage d’urgence). Le rôle d’un pilote est alors de contrôler l’aéronef dans des situations incertaines. Nous proposons un modèle basé sur une logique non-monotone, plus spécifiquement la logique des défauts, permettant de gérer l’information incomplete, incertaine et contradictoire. Enfin, nous présenterons un système de contrôle pour le pilotage d’un avion.

  • 12 juin 2017 : 14h00 at Amphi Herbrand (Luminy)
    ‘‘Inférence des causes moléculaires des switches phénotypiques.’‘
    by Célia Biane (IBISC)
    See abstract

    Inférence des déterminants moléculaires des switches phénotypiques. Un défi majeur de la recherche contre le cancer est de déterminer les mutations génétiques responsables des phénotypes cancéreux des cellules et inversement, des actions de médicaments permettant l’initiation de la mort de ces cellules cancéreuses. Un tel défi requiert d’établir des relations causales entre les effets moléculaires des mutations et des médicaments à leur conséquence sur les phénotypes. Nous proposons un cadre théorique où les mutations et les actions des médicaments sont représentées comme des modifications topologiques des réseaux moléculaires provoquant une reprogrammation du phénotype cellulaire. Nous introduisons les réseaux Booléens contrôlés qui permettent l’implémentation d’actions topologiques par des variables de contrôle et proposons un algorithme d’inférence des actions minimales causales permettant d’atteindre des comportements attendus aux états stables de la dynamique. Enfin, nous validons notre approche sur un modèle de régulation du switch apoptosis/prolifération en inférant de façon automatique des gènes causaux et des cibles thérapeutiques du Cancer du Sein.

    Inference of the molecular determinants of phenotypic switches. A major challenge in cancer research is to determine the genetic mutations causing the cancerous phenotype of cells and conversely, the actions of drugs initiating programmed cell death in cancer cells. However, such a challenge is compounded by the complexity of the genotype-phenotype relationship and requires to relate the molecular effects of mutations and drugs to their consequences on cellular phenotypes. We propose a theoretical framework where mutations and drug actions are seen as topological perturbations of molecular networks inducing cell phenotypic reprogramming. We introduce Boolean control networks where these topological network actions are modelled by control parameters. Based on this framework, we present a new algorithm using abductive reasoning principles that infers the minimal causal topological actions leading to an expected behavior at the stable states of the dynamics. We validate the framework on a model of network regulating the proliferation/apoptosis switch by automatically discovering driver genes and therapeutic targets in Breast Cancer.

  • 16 mai 2017 : 14h30 at Salle de réunion du modulaire (Luminy)
    ‘‘Modélisation déclarative des réseaux de régulation génique dus à R. Thomas, en programmation logique “non monotone”.’‘
    by Laurent Trilling (TIMC-IMAG)
    See abstract

    A. Rocca, E. Fanchon, L. Trilling. lab.TIMC-IMAG, Université de Grenoble, France.

    Nous nous intéressons à la modélisation déclarative des réseaux logiques de régulation génique proposés par René Thomas. Par approche déclarative, nous entendons : représentation de toutes les données biologiques disponibles (sur la structure ou la dynamique), sous forme d’axiomes logiques (contraintes) et obtention sous forme intensionelle (implicite) des réseaux de Tomas cohérents avec ces données en cas de satisfaisabilité. Pour ce faire, nous nous appuyons sur la technologie de programmation logique ASP (Answer Set Programming). Cette technologie est basée sur une logique non monotone n’autorisant que certains types de modèles logiques, dits stables: intuitivement, ne sont vrais que les atomes qui sont prouvables grâce aux axiomes. Un modèle stable est minimal en ce sens que de la suppression d’un atome d’un modèle ne peut résulter un modèle.

    Nous présenterons les grandes lignes de cette spécification logique en soulignant les choix de modélisation et en mettant en évidence, à l’aide d’exemples, les avantages de l’approche, comme la réparation automatique d’inconsistance ou l’apprentissage de toutes les propriétés, restreintes à une formulation fixée (par exemple les clauses d’une taille limitée sur un ensemble déterminé d’atomes), déductibles de tous modèles cohérents avec les données.

    Par ailleurs, nous aborderons l’apport de la non monotonie de la logique sous-jacente à ASP. Deux avantages généraux d’ASP sont reconnus : un traitement des données incomplètes radical (les atomes non prouvables sont réputés faux) et un pouvoir de déduction augmenté (les modèles stables forment un sous-ensemble des modèles). Nous nous consacrerons plutôt à trois aspects précis : 1) l’utilisation de défauts pour spécifier la réparation d’inconsistance en montrant l’intérêt d’exprimer la minimisation sous-jacente en termes logiques (et non pas algorithmiques), 2) l’emploi (et la méthodologie de construction) d’une conjonction de défauts originale pour exprimer la notion de composition d’interactions géniques seulement généralement vraie (i.e. sauf à être prouvée effectivement fausse), 3) la mise en œuvre de formules CTL générales, en particulier du type AF (indispensables pour exprimer des propriétés exhaustives sur les comportements), en prenant appui sur la minimalité des modèles stables.

  • 24 avril 2017 : 10h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Sandpiles and graph polynomial.’‘
    by Kévin Perrot
    See abstract

    We will first play with a sandpile simulator and exhibit its surprising algebraic properties, then see how sand dynamics can be used to talk about the graph itself and progress towards the definition of a directed analogue to the Tutte polynomial.

    Joint work with Trung Van Pham, “Chip-Firing game and partial Tutte polynomial for Eulerian digraphs”, Electronic Journal of Combinatorics, volume 23, issue 1, 2016.

  • 14 février 2017 : 14h15 at Salle de réunion du modulaire (Luminy)
    ‘‘Domptage de substitutions bi-dimensionnelles.’‘
    by Timo Jolivet
    See abstract

    Le mot “substitution” correspond à plusieurs notions subtilement différentes, mais toutes liées à l’auto-similarité. Nous verrons comment aller d’une définition rigide/géométrique vers une définition plus flexible/combinatoire, en illustrant le tout par des applications et beaucoup d’exemples.

  • 31 janvier 2017 : 14h15 at Salle de réunion du modulaire (Luminy)
    ‘‘Des logiques non-monotones aux systèmes dynamiques discrets (SDD).’‘
    by Pierre Siegel
    See abstract

    Du point de vue logique et représentation des connaissances, un système biologique peut être considéré comme un ensemble d’éléments qui interagissent entre eux. Par exemple une cellule est un ensemble de protéines/gênes qui interagissent pour la faire survivre se reproduire et mourir. Pour l’Intelligence Artificielle la cellule pose des problèmes intéressants. Il faut d’abord formaliser les interactions, mais une formalisation en logique « classique » est difficile car elle donne des incohérences. Ensuite ce que l’on sait vient en grande partie d’expériences longues et coûteuses. On ne connaît donc qu’une petite partie des interactions et cette connaissance peut être révisable, incertaine, contradictoire et fausse. Il faut aussi essayer de compléter les interactions in-silico. D’autre part la complexité algorithme est importante et il est nécessaire de donner des techniques pour donner des temps de calcul raisonnables dans la pratique. Ces questions sont étudiées depuis longtemps en IA en utilisant en particulier des logiques non-monotones et des techniques issues de la programmation par contraintes. Des résultats ont été obtenus avec Andrei Doncescu et Tan Le [1] en utilisant la logique des défauts.

    D’un autre côté, les systèmes biologiques peuvent être étudiés dans le contexte des réseaux d’automates et des SDD. Des théorèmes fondateurs ont porté sur les cycles d’interactions et leur étude est fondamentale. Mais une représentation des SDD par la logique des défauts (et par la plupart des logiques non-monotones) n’est pas adaptée. Par exemple l’équivalent d’un circuit impair n’a pas d’extension (de solution, de point fixe..). Cette absence d’extension pour les logiques des défauts a été étudiée avec Camilla Schwind [2]. Cette étude a donné la Logique des Hypothèses. Pour cette logique on a toujours des extensions mais certaines de ces extensions, bien caractérisées (les extensions fantômes) sont spéciales et leur utilité n’était pas claire.

    Avec Sylvain Sené et Andrei Doncescu nous étudions une représentation des SDD par la logique des hypothèses. Un but est de permettre de discriminer les états stables, les cycles stables et les cycles instables. Les extensions fantômes semblent permettre de le faire. Un autre but est de donner des algorithmes efficaces pour calculer les cycles stables et instables. Quelques premiers résultats seront présentés.

    [1] Andrei Doncescu and Pierre Siegel. Emerging Trends in Computational Biology, Bioinformatics, and Systems Biology, chapter DNA Double-Strand Break–Based Nonmonotonic Logic, pages 409–427. In Emerging Trends in Computer Science and Applied Computing. Elsevier, August 2015.

    [2] P. Siegel, C. Schwind (93) Modal logic based theory for nonmonotonic reasoning. Journal of Applied Non classical Logic, vol 3 - n° 1/1993, P 73-92.

  • 17 janvier 2017 : 14h30 at Salle de réunion du modulaire (Luminy)
    ‘‘Let’s compute through infinite time!’‘
    by Sabrina Ouazzani (LACL)
    See abstract

    In this talk, we present infinite time Turing machines (ITTM), from the original definition of the model to some new infinite time algorithms.

    We will present algorithmic techniques that allow to highlight some properties of the ITTM-computable ordinals. In particular, we will study gaps in ordinal computation times, that is to say, ordinal times at which no infinite time program halts.

  • 9 janvier 2017 : 16h30 at Salle de réunion du modulaire (Luminy)
    ‘‘The gentleness of perturbations and the topological classification of quantum walks.’‘
    by Christopher Cedzich (University of Hannover)
    See abstract

    In this talk I present a topological classification of symmetric one-dimensional quantum walks. For each set of symmetries of the tenfold way, different classes of quantum walks are distinguished by a topological number, called the symmetry index of the walk. Like for systems in continuous time, this classification proves stable under perturbations homotopic to the identity (so-called gentle perturbations). Moreover, I will show that stability against non-gentle perturbations can be achieved and additional invariants are introduced which no not have a counterpart in the Hamiltonian case. As an application I will provide a simple proof of bulk-edge correspondence for one-dimensional quantum walks.

    https://arxiv.org/abs/1611.04439

    References:

    Bulk-Edge Correspondence of one-dimensional Quantum Walks
    C. Cedzich, F. A. Grünbaum, C. Stahl, L. Velázquez, A. H. Werner and R. F. Werner
    Journal of Physics A: Mathematical and Theoretical 49(21): 21LT01, 2016.
    arXiv:1502.02592

    A topological classification of one-dimensional symmetric quantum walks
    C. Cedzich, T. Geib, F. A. Grünbaum, C. Stahl, L. Velázquez, A. H. Werner and R. F. Werner
    In preparation.

  • 13 décembre 2016 : 14h00 at Salle de réunion du 3e étage de la FRUMAM (Saint-Charles).
    ‘‘Points fixes dans les réseaux booléens monotones.’‘
    by Adrien Richard (I3S)
    See abstract

    Les réseaux booléens sont des systèmes dynamiques où chaque variable ne peut prendre que deux états possibles: 0 ou 1. Depuis les travaux pionniers de Kauffman et Thomas, ce sont des modèles très classiques pour les réseaux de gènes. Dans ce contexte, les points fixes sont d’un intérêt particulier: ils correspondent à des patterns stables d’expression des gènes souvent reliés à des fonctions cellulaires bien précises. Cependant, les premières informations disponibles sur un réseau de gènes concernent généralement le graphe d’interaction du réseau et non sa dynamique. Une question naturelle est donc la suivante: que peut-on dire sur les points fixes d’un réseau booléen en fonction de son graphe d’interaction seulement ? Dans cette exposé, on présente une étude du plus grand nombre de points fixes qu’un réseau booléen monotone peut admettre en fonction de son graphe d’interaction. On donnera des bornes inférieures et supérieures qui ne dépendent que de la structure des cycles du graphe d’interaction. Les deux paramètres centraux seront, d’une part, la taille d’un plus petit ensemble de sommets intersectant tous les cycles et, d’autre part, le plus grand nombre de cycles disjoints. L’étude fera intervenir des théorèmes, classiques en combinatoire, sur le treillis booléen et ses antichaines. C’est un travail réalisé en collaboration avec Julio Aracena et Lilian Salinas (Université de Concepcion, Chili) disponible à l’adresse suivante: http://arxiv.org/abs/1602.03109.

  • 11 octobre 2016 : 14h00 at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Marches quantiques : simulation d’un fluide relativiste.’‘
    by Mohamed Hatifi (Institut Fresnel)
    See abstract

    L’avènement de la physique quantique et des principes de relativité ont permis une meilleure compréhension du monde dans lequel nous vivons. La physique étant une science expérimentale, il est souvent nécessaire, dans un premier temps, d’avoir recours aux modélisations numériques. L’objet de cette présentation est de mettre au goût du jour la notion de fluide relativiste et de montrer comment nous pouvons le modéliser en utilisant un modèle basé sur les marches quantiques aléatoires. En quelques mots, ces marches sont définies comme analogue des marches classiques et sont depuis peu utilisées dans un large panel d’application: de l’optimisation d’algorithmes quantiques aux simulations de systèmes sans équivalents classiques. Il sera utile dans un premier temps de rappeler les concepts théoriques liés à ces marches, puis dans un deuxième temps, nous appliquerons ce formalisme à un cas particulier de solution puis nous interprèterons les résultats en s’appuyant sur des concepts d’hydrodynamique et d’optique géométrique.

  • 4 mai 2016 : 14h00 at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Influence et causalité dans les simulations de Kappa.’‘
    by Ioana Cristescu (Postdoc Harvard Medical School)
    See abstract

    Kappa est un language formel pour décrire l’interaction entre protéines. Les réactions moléculaires sont représentées par des règle de réécriture sur des graphes. À chaque règle on associe un taux cinétique, qui est la vitesse de la réaction. Le simulateur de Kappa, Kasim, va engendrer des simulations stochastiques à partir d’un ensemble de règles et d’un graphe initial. Un événement de la simulation consiste en une règle et une injection de cette règle dans le graphe. KaSim intègre aussi des outils qui permettent des analyses statiques et dynamiques du système. Au cours de mon exposé je vous présenterai ces outils, qui nous permettrons de parler des relations d’influence, de causalité ou de temporalité entre ces événements. Souvent, on construit un modèle Kappa à partir d’un texte biologique. Toutefois, certains affirmations, comme influence d’un processus sur un autre, ne peuvent être représentées comme des règles de réécriture. Plutôt que décrire un comportement, ces affirmations servent à vérifier la validité du système. Intégrer ces affirmations dans le modèle fait partie de mon travail en cours. On regardera comment on peut utiliser les relations entre événements induits par l’analyse statique et dynamique pour vérifier les affirmations d’influence.

  • 13 avril 2016 : 13h30 at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Self-shuffling words.’‘
    by Svetlana Puzynina (ENS Lyon)
    See abstract

    An infinite word x is self-shuffling, if x admits factorizations: $x=\prod_{i=1}^\infty U_iV_i=\prod_{i=1}^\infty U_i=\prod_{i=1}^\infty V_i$, where U_i,V_i are finite words. In other words, there exists a shuffle of x with itself which reproduces x. W­­e prove that many important and well studied words are self-shuffling: This includes the Thue-Morse word and all Sturmian words except Lyndons. We further establish a number of necessary conditions for a word to be self-shuffling, and show that certain other important words (including the paper-folding word and infinite Lyndon words) are not self-shuffling. This new notion has some unexpected applications: As a consequence of our characterization of self-shuffling Sturmian words, we recover a number theoretic result, originally due to Yasutomi, on a classification of pure morphic Sturmian words in the orbit of the characteristic. Finally, we provide a positive answer to a recent question by T. Harju whether square-free self-shuffling words exist and discuss self-shuffling in a shift orbit closure.

  • 12 avril 2016 : 14h at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Méthodes de modélisation algébrique et d’analyse des réseaux de régulation biologique.’‘
    by Maxime Folschette (I3S)
    See abstract

    La modélisation qualitative des réseaux de régulation biologique consiste à représenter les systèmes d’interactions sous forme d’automates et de paramètres discrets plutôt que d’équations différentielles continues. Cela a permis de grandement réduire la complexité de l’analyse des comportements dynamiques des modèles en passant d’un cadre continu à un cadre discret ou hybride. Au cours de ce séminaire, je présenterai mes travaux dans le domaine de la modélisation et de l’analyse dynamique des modèles biologiques discrets. Ceux-ci se concentrent sur différentes sous-classes des modèles d’automates, dont fait notamment partie le très répandu modèle de Thomas, et sur différentes méthodes pour étudier leur comportement dynamique. Je présenterai notamment une méthode d’analyse statique par interprétation abstraite, qui permet de vérifier des propriétés d’accessibilité dans de très grands modèles avec une complexité très faible, ainsi qu’une approche reposant sur le µ-calcul polyadique, qui est une extension des logiques temporelles classiques (LTL et CTL) permettant de représenter une plus large palette de propriétés dynamiques.

  • 11 avril 2016 : 14h at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Des automates cellulaires réversibles aux transformations causales et quantiques de graphes.’‘
    by Simon Martiel (Postdoc LSV, Paris)
    See abstract

    Les automates cellulaires décrivent l’évolution d’une grille discrète sous des contraintes inspirées de la physique: une portion bornée de la grille contient une quantité bornée d’information, l’information voyage à vitesse bornée au sein de la grille, et les lois d’évolutions de la grille sont les mêmes en tout endroit et tout temps. Un résultat élégant de la théorie des automates cellulaires réversibles (ACR) est que tout ACR peut être décrit comme un circuit de profondeur bornée d’opérations locales et réversibles. Dans cette présentation nous présenterons ce résultat, ainsi qu’une généralisation de celui-ci à un modèles d’automates cellulaires sur géométries dynamiques: les dynamiques causales de graphes. Enfin nous montrerons comment ce résultat peut-être utilisé pour caractériser d’une part les Automates Cellulaires Quantiques, et d’autre part les dynamiques causales quantiques.

  • 5 avril 2016 : 14h45 at Amphi 12, Luminy
    ‘‘Optimality of entropic uncertainty relations.’‘
    by Philippe Raynal (National University of Singapore)
    See abstract

    Heisenberg’s uncertainty principle states that, for any quantum state, the probability distributions of two non-commuting observables cannot be arbitrarily and simultaneously peaked. A famous example is the tradeoff between Which-Path information and Interference strength in a two-path interferometer, an instance of wave-particle duality. The modern form of the uncertainty principle is due to Robertson and takes the form of an inequality relating the standard deviations of the two distributions and the commutator of the two corresponding observables. Uncertainty relations can also be expressed in terms of other measures of information like Shannon and Réniy entropies. However, the entropic uncertainty relation derived by Maassen and Uffink, a lower bound on the sum of two entropies for an arbitrary pair of observables, is not optimal in the sense that in general the inequality cannot be saturated.

    Our goal is to find optimal entropic uncertainty relations in finite dimensions. Therefore in this talk, we will go beyond the Maassen and Uffink relation to investigate the curve of minimal entropy. We will disproof a conjecture, generalise various results, and propose new conjectures.

    Article: K. Abdelkhalek, R. Schwonnek, H. Maassen, F. Furrer, J. Duhme, P. Raynal, and B.-G. Englert, and R. F. Werner
    arXiv.org/pdf/1509.00398.pdf
    Int. J. Quantum Inform. 13, 1550045 (2015)

  • 5 avril 2016 : 10h at Salle de réunion du 5e (TPR1, entrée G, 5e étage)
    ‘‘Autour de la connexité dans les graphes avec conflits.’‘
    by Benjamin Momège (Postdoc Inria, Lille)
    See abstract

    Nous nous intéresserons aux graphes avec conflits (un conflit est une paire d’arêtes ne pouvant pas simultanément faire partie d’un sous-graphe), dans lesquels nous étudierons différents types de problèmes, de nature aussi bien algorithmique que combinatoire, notre ligne directrice étant la notion de connectivité. Nous verrons que plusieurs résultats, simples sans conflit, ne le sont plus lors de l’ajout de conflits. Nous présenterons : des algorithmes exacts (non polynomiaux), des résultats de NP-complétude, et des conditions suffisantes assurant l’existence de certains objets (arbre couvrant, chemin et cycle Hamiltonien) sans conflits.

  • 4 avril 2016 : 16h30 at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Introduction au calcul uniforme : élection de leader sur les automates cellulaires à entrée périodique.’‘
    by Nicolas Bacquey (ATER GREYC, Caen)
    See abstract

    Tous les modèles de calcul usuels présentent une “singularité” qui permet de démarrer un calcul : tête d’une machine de Turing, état initial, cellule au bord de la configuration d’un automate cellulaire… Est-il possible de définir une notion de calcul sur un modèle dénué d’un maximum de ces singularités ? Comment présenter l’entrée, comment lire un résultat ? Comment définir une complexité ?

    On tentera de répondre à ces questions dans le modèle de calcul des automates cellulaires à configuration périodique, modèle dans lequel à la fois la donnée et le programme sont uniformes dans l’espace. Plus précisément, on présentera une famille d’algorithmes réalisant l’élection de leader sur ces configurations périodiques.

    Il est impossible d’élire une unique cellule de la configuration par définition ; les algorithmes présentés utilisent des techniques permettant de transformer des différences spatiales en différences temporelles, induisant des ruptures de symétrie. Ainsi, on parvient à élire une unique classe d’équivalence de cellules de la configuration.

  • 21 mars 2016 : 16h30 at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Quantum Walks Gravity Simulation.’‘
    by Giuseppe Di Molfetta (Postdoc Instituto de Fisica Corpuscular (IFIC), Universitat de València)
    See abstract

    As we know, spacetime is not flat at the cosmological scale. In order to describe spacetime, in General Relativity theory (GR), we need a continuous and differentiable manifold and a formal way to account for the continuous distortion of the metrics. The main point is that changing coordinate systems should not affect physics laws (General Covariance). However at the Planck length, matter is not continuous and obeys Quantum Theory (QT). Although one century has passed, finding an intrinsically discrete counterpart of GR is still an open question. In fact, discretized GR does not turn out in just a mere finite difference scheme of the old formula.

    I recently showed that one way to describe a discrete curved spacetime is by using Quantum Walks. From a physical perspective a QW describes situations where a quantum particle is taking steps on a discrete grid conditioned on its internal state (say, spin states). The particle dynamically explores a large Hilbert space associated with the positions of the lattice and allows thus to simulate a wide range of transport phenomena.

    It is surprising that this unitary and local dynamics, defined on a rigid space-time lattice coincides in the continuous limit with the dynamical behavior of a quantum spinning-particle spreading on a curved spacetime. This could really turn out to be a powerful quantum numerical method to discretize GR.

  • 7 mars 2016 : 14h at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Etude de la puissance d’expression et de l’universalité des modèles de calcul inspirés par la biologie.’‘
    by Sergiu Ivanov (ATER LACL, Paris)
    See abstract

    In this presentation, we will consider the problems of computational completeness and universality for several biologically-inspired models of computation: insertion-deletion systems, networks of evolutionary processors, and multiset rewriting systems. The presented results fall into two major categories: study of expressive power of the operations of insertion and deletion with and without control, and construction of universal multiset rewriting systems of low descriptional complexity.

    Insertion and deletion operations consist in adding or removing a subword from a given string if this subword is surrounded by some given contexts. The motivation for studying these operations comes from biology, as well as from linguistics and the theory of formal languages. In the first part, we focus on insertion-deletion systems closely related to RNA editing, which essentially consists in inserting or deleting fragments of RNA molecules. We show that allowing one-symbol insertion and deletion rules to check a two-symbol left context enables them to generate all regular languages. Moreover, we prove that allowing longer insertion and deletion contexts does not increase the computational power. We further consider insertion-deletion systems with additional control over rule applications and show that computational completeness can be achieved by systems with very small rules.

    The second part of the presentation is concerned with the universality problem, which consists in finding a fixed element able to simulate the work any other computing device. We start by considering networks of evolutionary processors (NEPs), a computational model inspired by the way genetic information is processed in the living cell, and construct universal NEPs with very few rules. We then focus on multiset rewriting systems, which model the chemical processes running in the biological cell. For historical reasons, we formulate our results in terms of Petri nets. We construct a series of universal Petri nets and give several techniques for reducing the numbers of places, transitions, inhibitor arcs, and the maximal transition degree. Some of these techniques rely on a generalisation of conventional register machines, proposed in this thesis, which allows multiple register checks and operations to be performed in a single state transition.

  • 23 fevrier 2016 : 10h at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Calculs universels et comportements asymptotiques en dynamique symbolique.’‘
    by Benjamin Hellouin (Postdoc Andrés Bello University, Santiago)
    See abstract

    L’étude mathématique des systèmes dynamiques cherche à prévoir le comportement à long terme et à grande échelle d’un système à partir d’une information locale et limitée. La plupart des problèmes de prédiction se révèlent cependant indécidables dans le cas général, et la preuve de tels résultats passe souvent par la simulation, au sein du système considéré, de calcul universel sous une certaine forme. Les constructions nécessaires à ces simulations dépendent grandement du problème étudié, ce qui contraste avec l’idée naive d’une Turing-universalité “généraliste” qui rendrait tous les problèmes pertinents indécidables.

    Dans cet exposé, je ferai un panorama de ma recherche portant sur deux systèmes dynamiques discrets suivant cette approche : les automates cellulaires et la fourmi de Langton. Pour les automates cellulaires, le problème étudié est celui de décrire le comportement asymptotique typique partant d’une configuration initiale tirée au hasard. Avec Mathieu Sablik puis Martin Delacourt, nous avons montré que ce problème est indécidable dans le cas général; je comparerai la simulation de calcul universel impliquée dans la preuve de ce résultat avec les nombreuses autres formes connues dans les automates cellulaires, et la manière dont elles sont affectés par certaines restrictions dynamiques. Pour la fourmi de Langton, j’exposerai des travaux en cours en collaboration avec Anahi Gajardo et Diego Maldonado, dans lesquels nous cherchons à mettre en relation la complexité de la trajectoire de la fourmi et sa capacité à simuler du calcul universel sous différentes formes.

  • 22 fevrier 2016 : 14h at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Directional Dynamics along Arbitrary Curves in Cellular Automata.’‘
    by Martin Delacourt (ATER LORIA, Nancy)
    See abstract

    This is a joint work with Victor Poupet, Mathieu Sablik and Guillaume Theyssier.

    Cellular automata (CA) are discrete dynamical systems with homogeneous and local evolution rule. We consider the one-dimensional case, that is CA with configurations in X^{Z} for some finite alphabet X. We can study classical dynamical properties like equicontinuity and expansivity, and Petr Kurka proposed in 1997 a classification of all CA according to these properties that describe the flows of informations in the evolutions of a CA.

    The shift is a specific CA that plays a crucial role in the world of CA, and in particular commutes with any other CA. Considering this, Mathieu Sablik gave in 2008 a new classification that considers the properties of equicontinuity and expansivity along linear directions, that is composing the CA with a constant and rational power of the shift. This gave rise to the notions of sets of directions of equicontinuity or expansivity.

    Here we enlarge the scope again and consider every possible direction. We prove a new version of the classification, provide various examples that show that this extension is meaningful and in particular we characterize the real numbers that can be the limit of sets of directions for equicontinuous dynamics.

  • 16 fevrier 2016 : 10h at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Coherent activity in excitatory pulse-coupled networks.’‘
    by Simona Olmi (INS, AMU)
    See abstract

    An excitatory pulse-coupled neural network is a network composed of neurons coupled via excitatory synapses, where the coupling among the neurons is mediated by the instantaneous transmission of action potentials. The coherent activity of a neuronal population usually indicates that some form of correlation is present in the dynamics of the considered neurons.

    The role played by the topology in promoting coherent activity in excitatory diluted pulse-coupled neural networks at a microscopic and macroscopic level is investigated. In particular, we consider a diluted random network where neurons were connected as in a directed Erdös-Renyi graph with average connectivity (in-degree) scaling linearly with the number of neurons in the network. In these “massively connected” networks we show that in the infinite size limit the dynamics of coherent collective states coincide with that of fully coupled networks. However, the random dilution of the connections induces inhomogeneities in the neuronal behaviors for any finite system size, promoting a weak form of chaos, which vanishes in the limit of infinite size. In this limit, the random systems exhibit regular (non chaotic) dynamics thus recovering the properties of a homogeneous fully connected network.

    The situation is quite different for a “sparse network” characterized by a constant connectivity (in-degree), independent on the size of the network. In fact, on one side we show that a few tens of random connections are sufficient to sustain a nontrivial collective dynamics. In other words, collective motion is a rather generic and robust property and does not require an extremely high connectivity to be sustained. On an other side, the collective dynamics coexists with a microscopically chaotic dynamics that does not vanish in the thermodynamic limit and turns out to be extensive (i.e. the number of unstable directions is proportional to the network size). Extensive chaos has been already found in spatially extended system with nearest-neighbour coupling (diffusive coupling) induced by the additivity of the system. In this case this property is highly nontrivial, as the network dynamics is non additive and it cannot be approximated as the juxtaposition of almost independent sub-structures.

    Finally the dynamics of two symmetrically coupled populations of pulse-coupled neurons is considered: this is the simplest instance of “network-of-networks”, that is often invoked as paradigm for neural system. Upon varying both the self-coupling and the cross-coupling strengths various kinds of collective states were found: in particular the phase diagram of the system reveals various kinds of symmetric and symmetry broken collective states ranging from splay states to tori, from chimera states to collective chaos.

    S. Olmi, R. Livi, A. Politi and A. Torcini, Physical Review E 81, 046119 (2010).
    L. Tattini, S. Olmi, A. Torcini, Chaos 22, 023133 (2012).
    S.Luccioli, S. Olmi, A. Politi, A. Torcini, Phys. Rev. Lett. 109, 138103 (2012).
    S. Olmi, A. Politi and A. Torcini, EPL 92, 60007 (2010).

  • 15 fevrier 2016 : 14h at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Condition combinatoire nécessaire et suffisante pour les corrélations Non-locales Causales.’‘
    by Julien Degorre (PCQC, Paris)
    See abstract

    Using a quantum particle as a support of information has led researchers to redefine the computer science from information theory to algorithm and complexity. A quantum computer can provide a huge advantage over a classical computer for some specific tasks (Shor’s algorithm and Quantum cryptography…), but it is certainly not true for all tasks.

    The problem is, in which case quantum computer is better than classical computer ? How quantifying the power of quantum resources with respect to classical resources ?

    In almost all example where a quantum computer has a clear advantage over classical, it involves quantum non-locality, means a non-signalling correlation stronger than any classical correlation.

    Here to characterize this non-local correlations with respect of the classical one, I will introduce new approach which doesn’t involves any Quantum physics but only combinatory. I will show a simple, necessary and sufficient Combinatorial condition to characterize the Non-signalling (i.e. causal) correlations. Moreover, this approach will give us intuitive view of the structure of causal probabilities distribution, or non signalling correlations.

    NOTE: An effort will done to introduce any prerequisites during the talk to be able to match with an eclectic audience (computer scientist, physicist, math…)

  • 8 fevrier 2016 : 14h at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Symmetry in classical logics and its extension to non-monotonic logics and reasoning.’‘
    by Belaid Benhamou (LSIS)
    See abstract

    La symétrie est par définition un concept multidisciplinaire. Il apparaît dans de nombreux domaines allant des mathématiques à l’intelligence artificielle, de la chimie et de la physique. Il révèle des formes et des usages différents, même à l’intérieur du même domaine. En général, il renvoie à une transformation qui laisse invariant (ne pas modifier sa structure fondamentale et / ou ses propriétés ) un objet (un chiffre, une molécule, un système physique, une formule ou un réseau de contraintes). Par exemple, la rotation d’un échiquier jusqu’à 180 degrés donne un échiquier qui est indiscernable de celui d’origine. La symétrie est une propriété fondamentale qui peut être utilisée pour étudier ces différents objets, analyser finement ces systèmes complexes ou réduire la complexité de calcul lorsqu’il s’agit de problèmes combinatoires.

    La symétrie a été bien étudiée dans les logiques classiques et la programmation par contraintes depuis plus d’une décennie. Au début, Krishnamurthy a montré que certaines formules difficiles admettent de courtes démonstrations lors de l’extension du système de preuve par résolution de la logique propositionnelle par la règle de symétrie. Le groupe de Marseille (Benhamou, Sais et Siegel) travaillant sur la symétrie a développé le principe des symétries dans les années 1990, a montré comment les symétries peuvent être détectées et utilisées efficacement dans les solveurs SAT (logique propositionnelle) et solveurs CSP (Benhamou 94). Toutefois, en Intelligence Artificielle, on manipule souvent des informations incomplètes et nous devons inclure l’incertitude pour raisonner avec des connaissances contenant des exceptions et la non-monotonie. Plusieurs logiques non classiques sont introduits à cet effet, mais pour autant que nous savons, la notion de symétrie pour ces cadres n’avaient pas encore été étudiée.

    Dans cet exposé, nous parlerons d’abord de cette notion de symétrie dans les logiques classiques, ensuite nous montrons comment elle est étendue récemment à des logiques non- monotones comme les logiques préférentielles, les X-logiques et la logiques des défauts. Nous donnons de nouvelles règles d’inférence en utilisant la symétrie pour les X-logiques et la logique des défauts. Nous montrons comment mettre en œuvre le raisonnement par symétrie pour ces logiques non-monotones et nous prouvons que certaines symétries qui n’existent pas dans les logiques classiques sont bien présentes dans ces formalismes.

    Enfin, nous avons choisi le cadre des ASP (Answer Set Programming) pour mettre en œuvre et implémenter la symétrie dans le raisonnement non-monotone. L’ASP est un cadre non-monotone très utilisé, il est considéré comme un fragment de la logique des défauts. Nous parlerons ici de la notion des symétries locales et celle des symétries globales. Nous montrons comment les symétries locales d’un programme logique peuvent être détectées de manière dynamique au moyen des automorphismes de sa représentation graphique. Nous donnons également des propriétés qui permettent d’éliminer les symétries dans les solveurs ASP afin d’améliorer leurs efficacités.

  • 1 fevrier 2016 : 14h at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Approche comportementale pour la biologie : vers une automatisation de la conception des fonctions de synthèse.’‘
    by Adrien Basso-Blandin (Postdoc ENS Lyon)
    See abstract

    La biologie possède une masse de connaissances dont la disparité des données et la fragmentation entraine une difficulté d’appréhension des systèmes dans leur globalité.
    Plus particulièrement, en biologie de synthèse où l’objectif est de concevoir de nouvelles fonctionnalités n’existant pas à l’état naturel à partir de composants existants, la connaissance partielle de ces composants entraine de lourds risques de sécurité et de sureté lors de l’assemblage de nouveaux organismes.

    Dans ce cadre, nous proposons un grand axe majeur centré sur la définition d’une tour de modèles formels permettant dans le cas le plus abstrait une description comportementale des fonctionnalités des systèmes et dans celui le plus concret de décrire les interactions mécanistiques entre composants élémentaires.

    L’objectif à terme est de proposer à la communauté des biologistes un ensemble d’outils d’aide à la décision permettant l’agrégation de connaissances biologiques en une unique représentation de connaissances, puis l’inférence de nouvelles connaissances ainsi que la validation et la vérification formelle et in-vitro lors de la conception de nouvelles fonctions biologiques.

  • 16 novembre 2015 : 14h30 at Salle de séminaire du 5e au LIF (TPR1, entree G, 5e etage)
    ‘‘Computational complexity of majority boolean networks under different updating schemes’‘
    by Pedro Montealegre (PhD LIFO, Orléans)
    See abstract

    Given a threshold boolean network, as well as an updating scheme over its vertices, we study the computational complexity associated with the prediction of the future state of a vertex. An updating scheme can be synchronous (each vertex is updated at the same time), sequential (vertices are updated one by one in some fixed order) or block-sequential. We show that the prediction problem for synchronous and sequential updating schemes is P-Complete even when the input graph is cubic (3-regular) and is PSPACE-Complete for block sequential updating schemes.

  • 16 juin 2015 : 14h at Amphi 12 (bât. B, Luminy)
    ‘‘Intrinsic universality of causal graph dynamics’‘
    by Simon Martiel (PhD I3S, Nice)
    See abstract

    Causal Graph Dynamics generalize Cellular Automata, extending them to bounded degree, time varying graphs. The dynamics rewrites the graph in discrete time-steps, with respect to two physics-like symmetries: causality (there exists a bounded speed of information propagation) and shift-invariance (the rewriting acts everywhere the same). Intrinsic universality is the ability of the instance of a model to simulate all other instances, while preserving the structure of the computation. We present here an intrinsically universal family of Causal Graph Dynamics, and give insights on why it seems impossible to improve this result to the existence of a unique intrinsically universal instance.

  • 20 mai 2015 : 14h at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Quantum processes: an introduction’‘
    by Cédric Bény (ITP, Hannover)
    See abstract

    Nature is quantum. One essential way in which quantum theory differs from classical probability theory is that an unknown state cannot be copied. In other words, quantum information is conserved. This has profound consequences. For instance, it explains why quantum phenomena are hard to detect: any random interaction between a quantum system and its environment will take away information which cannot also be shared with an observer without being classical.

  • 11 mai 2015 : 14h at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Reversible Causal Graph Dynamics’‘
    by Pablo Arrighi
    See abstract

    Causal Graph Dynamics extend Cellular Automata to arbitrary, bounded-degree, time-varying graphs. The whole graph evolves in discrete time steps, and this global evolution is required to have a number of physics-like symmetries: shift-invariance (it acts everywhere the same) and causality (information has a bounded speed of propagation). We study a further physics-like symmetry, namely reversibility. Joint work with: Simon Martiel, Simon Perdrix.

  • 27 avril 2015 : 14h at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘l’Oritatami, un modèle de pliage co-transcriptionel’‘
    by Pierre-Etienne Meunier (Postdoc Aalto, Helsinki)
    See abstract

    Les molécules essentielles du vivant (ARN, protéines) sont produites par pliage de chaînes (de nucléotides, d’acides aminés) linéaires, et leur géométrie une fois pliées est d’importance primordiale pour l’accomplissement de leurs fonctions.

    De nombreux modèles ont été proposés pour comprendre comment ce pliage s’effectue, mais ils ont tous ignoré un aspect essentiel du mécanisme de pliage : le fait que les molécules commencent à se plier pendant qu’elles sont transcrites. Ce détail change radicalement la complexité du modèle : dans les modèles de pliage précédents (le modèle HP, par exemple), le problème de prévoir la conformation la plus probable est NP-⁠complet. Or, notre compréhension actuelle de la physique (calcul quantique) semble contredire que toutes les cellules du vivant résolvent ce type de problèmes rapidement pour produire les molécules dont elles ont besoin.

    L’Oritatami est un modèle qui tient compte de ce phénomène; notre principal objectif jusqu’à maintenant a été de programmer des structures, c’est-⁠à-⁠dire de comprendre les molécules “de l’intérieur”, en essayant d’en créer de nouvelles plutôt qu’en les observant de l’extérieur.

    Bonus : en m’invitant au LIF, vous gagnez un accès gratuit et illimité à un jeu en ligne : http://users.ics.aalto.fi/~meunier/oritatami.hml

  • 13 avril 2015 : 14h at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Fractals, indécidabilité et automates à plusieurs rubans’‘
    by Timo Jolivet (Postdoc IMT, Toulouse)
    See abstract

    On démontre que la propriété “être d’intérieur vide” est indécidable pour une famille simple et naturelle de fractals (définis par des systèmes de fonctions itérées affines 2D). Les méthodes utilisées font intervenir des automates à plusieurs rubans et une variante du problème de correspondance de Post. Ce travail a été réalisé en collaboration avec Jarkko Kari.

  • 23 mars 2015 : 14h at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Une (petite) promenade formelle sur les chemins du raisonnement et de l’argumentation’‘
    by Vincent Risch (LSIS)
    See abstract

    Après un rappel de quelques approches canoniques proposées ces dernières années en IA pour la formalisation du raisonnement et de l’argumentation, cet exposé sera consacré à la présentation d’un calcul issu des X-logiques [Siegel, Forget, 96], et destiné à la simulation d’un échange argumentatif entre deux agents formels. J’aborderai la question d’une articulation entre raisonnement et argumentation à partir de la représentation d’un agent artificiel raisonnant sur un ensemble d’attitudes possibles face à un argument donné, et comme préliminaire à la génération d’un nouvel argument donné en réponse par cet agent. En particulier, à partir du caractère paraconsistant des X-logiques, il est facile d’exhiber la matrice non–déterministe d’une logique quadri-valuée, matrice dont découle directement un calcul de type n–séquents. La réduction à un calcul de séquents classiques peut alors être opérée à partir de la méthode proposée par [Avron, Ben-Naim, Konikowska, 09]. Au final, la logique obtenue se présente comme une généralisation de la logique Source Processeur La Plus Générale (Most General Source-Processor Logic), ce qui permet en retour de considérer l’utilisation de cette dernière au sein de notre propre système argumentatif. Un lien inattendu avec la cumulatitivité de la X-logique sous-jacente est établi.

  • 09 mars 2015 : 14h at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Quelques axes de recherche de l’équipe MEB (Mathématiques, Évolution, Biologie)’‘
    by Gilles Didier (I2M)
    See abstract

    Sans avoir l’ambition d’être complètement exhaustive, la présentation exposera plusieurs thèmes de recherche actuellement explorés au sein de l’équipe “Mathématiques, Evolution, Biologie” de l’I2M, notamment:
    - La reconstruction d’états ancestraux (discrets et continus),
    - L’estimation des taux de spéciation-extinction à partir de données fossiles,
    - La mise en évidence de signatures génomiques d’événement de convergence évolutive,
    - La recherche de communautés dans les graphes biologiques…

  • 19 janvier 2015 : 14h at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Un peu de logique pour l’Intelligence Artificielle et utilisation à l’étude des voies de signalisation cellulaire’‘
    by Pierre Siegel
    See abstract

    L’exposé donne une introduction rapide à l’Intelligence Artificielle et à la représentation des connaissances en IA. On s’intéresse plus particulièrement aux logiques non monotones qui veulent traitent de l’information incomplète ou incertaine. On applique cela à la représentation et l’étude des voies de signalisation dans la cellule cancéreuse. On parlera aussi un peu d’algorithmes pratiquement utilisables.

  • 12 janvier 2015 : 14h at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Réseaux d’automates et questions diverses’‘
    by Sylvain Sené

  • 17 avril 2014 : 10h30 at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Joint Diagnosability of Distributed Discrete Event Systems’‘
    by Lina Ye (Postdoc INRIA CONVECS, Grenoble)
    See abstract

    Diagnosis reasoning is to detect possible faults that can explain the observations. The possibility to achieve such a diagnosis reasoning depends on the diagnosability of the system. Diagnosability is a crucial system property determining at design stage how accurate any diagnosis algorithm can be on a partially observable system. Most existing approaches for diagnosability analysis require the global order of observable events, which is however not always available. Hence, we study the systems where each component can only observe its own observable events to keep the internal structure private in terms of observations. First, we propose a new definition called joint diagnosability that requires only the local order of observable events. Second, we prove that verifying joint diagnosability is an undecidable problem when communications between different components are not observable. Third, we provide a sufficient algorithm to check this property. Finally, we show that this problem is decidable when communications are observable.

  • 15 avril 2014 : 11h at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Ensembles limites d’automates cellulaires associés à une mesure de probabilité’‘
    by Martin Delacourt (Postdoc CMM UChile, Santiago)
    See abstract

    Un automate cellulaire est un système dynamique composé d’une infinité de cellules qui ont un état choisi parmi un ensemble fini, n’interagissent qu’avec leurs voisines et évoluent de manière synchrone au moyen d’une règle commune. On s’intéresse au comportement asymptotique d’un tel objet, c’est à dire à l’ensemble des états globaux accessibles arbitrairement tard : l’ensemble limite. C’est un objet très étudié, avec de nombreux résultats à la clé. Ici, on se donne de plus une mesure de probabilité sur l’ensemble des états et on regarde l’ensemble des états du système accessibles à la fois arbitrairement tard et souvent. On s’intéressera aux questions de structure et aux propriétés de calculabilité de cet objet.

  • 11 avril 2014 : 9h30 at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Variabilité spatio-temporelle des épidémies: application au paludisme et au choléra’‘
    by Jean Gaudart (MCU-PH SESSTIM, AMU)
    See abstract

    Aujourd’hui, parmi les 106 pays où la transmission du paludisme est en cours, 81 pays mettent l’accent sur le contrôle, alors que 25 sont dans la phase de pré-élimination/élimination. Une des principales causes de l’échec des programmes de lutte est la forte hétérogénéité de la dynamique de transmission du paludisme. Entre la variabilité du climat, la dynamique des sociétés et le parasite il est souvent difficile d’identifier le poids et le rôle des différents facteurs de risque.

    Pour comprendre la dynamique de transmission du paludisme à l’échelle locale il est nécessaire d’analyser finement la cartographie dynamique des cas de paludisme en lien avec l’environnement.

    Tout d’abord, à l’échelle d’un village (Bancoumana, Mali), nous avons recherché des zones de risques différents. Pour cela il a été nécessaire de développer une méthode de découpage oblique du plan (SpODT), détectant de « frontières » entre ces zones.

    Pour mieux comprendre la relation pluie-paludisme, nous avons développé un modèle dynamique de transmission conduit par la pluviométrie, permettant de reproduire l’évolution temporelle des cas de paludisme, ainsi qu’un modèle de réaction-diffusion pour représenter la diffusion spatiale au sein d’un village.

    Cette meilleure connaissance de la dynamique du paludisme nous a conduits à proposer de nouvelles stratégies de lutte fondées sur la notion de diffusion à partir de réservoirs actuellement en cours d’évaluation au Sénégal.

    Le choléra est généralement considéré comme le prototype de la maladie liée à l’eau, en particulier du fait que Vibrio cholerae, l’agent du choléra, est d’abord un germe de l’environnement capable de se développer dans les eaux saumâtres des estuaires. Cette bactérie tolère aussi l’eau douce, surtout si la faible salinité est compensée par une chaleur importante et la présence de nutriments. De nombreuses études ont mis en évidence le caractère saisonnier du choléra. En octobre 2010 une épidémie de choléra est déclarée en Haiti. Elle deviendra la plus importante épidémie de choléra avec 493 069 cas et 6 293 décès en 1 an. Dès le départ, des modélisations mathématiques ont été publiées, mais, ne tenant pas compte de la réalité épidémiologique notamment du mode de démarrage, les prévisions étaient fausses au moment même de la publication. L’analyse précise du démarrage épidémique et la relation avec l’environnement a permis de démontrer l’importation de la maladie à partir du Népal, l’aspect violent du démarrage dans le bas Artibonite due à une contamination brutale et transitoire du fleuve, sans aucun lien avec une pluviométrie faible. Par contre, la dynamique de transmission c’est ensuite modifiée, plus liée à la pluie, tout en diminuant progressivement. Là encore, la connaissance de la dynamique de transmission a permis de proposer une stratégie de lutte ciblée actuellement en cours et soutenue par l’UNICEF, qui nous amènera à l’élimination à court terme.

    Gaudart J, Rebaudet S, Barrais R, Boncy J, Faucher B, Piarroux M, Magloire R, Thimothe G, Piarroux R. Spatio-temporal dynamics of cholera during the first year of the epidemic in Haiti. PLoS Negl Trop Dis. 2013 Apr 4;7(4):e2145.

    http://www.plosntds.org/article/info:doi/10.1371/journal.pntd.0002145

    Piarroux R, Barrais R, Faucher B, Haus R, Piarroux M, Gaudart J, Magloire R, Raoult D. Understanding the cholera epidemic, Haiti. Emerg Infect Dis. 2011 Jul;17(7):1161-8.

    http://wwwnc.cdc.gov/eid/article/17/7/11-0059_article.htm

    Gaudart J, Poudiougou B, Ranque S, Doumbo O. Oblique decision trees for spatial pattern detection: optimal algorithm and application to malaria risk. BMC Med Res Methodol. 2005 Jul 18;5:22.

    http://www.biomedcentral.com/1471-2288/5/22

    Gaudart J, Poudiougou B, Dicko A, Ranque S, Toure O, Sagara I, Diallo M, Diawara S, Ouattara A, Diakite M, Doumbo OK. Space-time clustering of childhood malaria at the household level: a dynamic cohort in a Mali village. BMC Public Health. 2006 Nov 21;6:286.

    http://www.biomedcentral.com/1471-2458/6/286

    Gaudart J, Touré O, Dessay N, Dicko AL, Ranque S, Forest L, Demongeot J, Doumbo OK. Modelling malaria incidence with environmental dependency in a locality of Sudanese savannah area, Mali. Malar J. 2009 Apr 10;8:61.

    http://www.malariajournal.com/content/8/1/61

    Gaudart J, Ghassani M, Mintsa J, Rachdi M, Waku J, Demongeot J. Demography and diffusion in epidemics: malaria and black death spread. Acta Biotheor. 2010 Sep;58(2-3):277-305.

    http://link.springer.com/article/10.1007/s10441-010-9103-z

  • 10 avril 2014 : 15h at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Fragments de mathématiques discrètes’‘
    by Michelangelo Bucci (Postdoc LIRMM, Montpellier)
    See abstract

    A la frontière entre l’informatique et les mathématiques, les mathématiques discrètes sont un domaine de recherche fascinant qui a des liens avec de nombreuses branches des deux disciplines. L’un des aspects les plus intéressants des mathématiques discrètes est en fait leur nature multidisciplinaire. Au cours du séminaire j’essayerai de mettre en évidence la façon dont cet aspect donne souvent de bons résultats lorsque les mathématiques discrètes entrent en contact avec d’autres domaines de recherche.

    Dans la première partie du séminaire, nous allons voir comment des résultats même très abstraits peuvent avoir de surprenantes applications pratiques et comment, vice-versa, les domaines d’application peuvent être une source d’inspiration pour le développement de nouvelles questions mathématiques.

    Dans la deuxième partie du séminaire, nous allons discuter de certains outils et des questions qui pourraient prendre avantage de la mise au point de nouveaux outils mathématiques discrets.

    Le séminaire mettra l’accent, en particulier, sur le domaine de la combinatoire des mots et de la théorie des réseaux, avec une attention particulière aux problèmes d’intérêt biologique et médical.

    Aucune connaissance mathématique particulière ne sera nécessaire, seulement des connaissances d’algèbre de base.

  • 13 mars 2014 : 10h at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Modeling the expression waves during the mouse segmentation’‘
    by Aitor Gonzalez (Postdoc TAGC, AMU)
    See abstract

    The vertebrate segmentation relies on oscillation of gene expression in presomitic mesodermal (PSM) cells that are synchronized by Notch pathway-dependent coupling. The phase of these oscillations is delayed in the anterior PSM cells relative to the posterior PSM cells (called here anterior phase shift). This anterior phase shift is commonly attributed to an anteriorly increasing period profile. In mouse, a crucial mechanism of the oscillators is the autoinhibitory feedback with delay of the Hes7 gene. However it is unclear how the anterior phase shift is regulated. Here, we find that a coupled delay differential equation (DDE) model of Hes7 reproduces the anterior phase shift if we assume an anterior-posterior gradient of coupling strength, intercellular delay or transcription rate. This model predicts smaller anterior phase shift for lower anterior values of these parameters, and this agrees with timelapse imaging of Hes7 promoter activity in Lfng KO embryos. This model also predicts longer segmentation period and smaller phase shift if the gradient of these parameters is shifted posteriorly. In agreement with these predictions, Fgf inhibitors shift the anterior-posterior Dll1 mRNA gradient posteriorly, increase the segmentation period and decrease the anterior phase shift. In summary, coupling and an anterior-posterior gradient of the Notch pathway might be important elements to explain the anterior phase shift of the segmentation clock.

  • 06 mars 2014 : 10h30 at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Reaction networks with delays applied to toxicity analysis’‘
    by Cinzia Di Giusto (Postdoc IBISC, Évry)
    See abstract

    Toxicology studies the adverse effects of the exposures to chemicals at various levels of living entities. I will propose a framework that aims at discovering the molecular mechanisms of toxicity. More precisely, I will introduce a modular modelling environment, called RaNDy for Reaction Networks with Delays. In RaNDy, systems consist of a set of species present in the environment at a given level. Species can degrade as time passes by and their presence is governed by a set of rules (reactions). In a reaction, species can have the role of reactants, inhibitors or products. A reaction has a given duration, and it can take place only if all reactants are available and all inhibitors are not for the whole duration of the reaction. Depending on the type of reaction, products levels are either increased or decreased. I will show how to model toxicogenomics problems, namely deregulation of homoeostatic processes, into formulae of a suitable temporal logic like CTL. The approach is applied to the study of the impact of the aspartame assimilation into the blood glucose regulation process.

  • 17 décembre 2013 : 15h at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Auto-assemblage non-coopératif de chemins et de carrés’‘
    by Pierre-Étienne Meunier (Postdoc LIAFA, Paris)
    See abstract

    L’auto-assemblage est un modèle de formation de structures moléculaires, capable de calcul Turing, mais aussi implémentable en pratique à l’aide de brins d’ADN. Dans cet exposé, je m’intéresserai à la variante non-coopérative de ce modèle, qui modélise une forme de croissance de cristaux par formation de branches. Enfin, je prouverai une vieille conjecture de Rothemund et Winfree : on ne peut pas assembler des carrés de taille n x n avec moins de 2n-1 tuiles. Cet exposé est basé sur le papier suivant : http://hal.archives-ouvertes.fr/hal-00912937.


Software

  • funkdigen2 : An efficient generator of functional digraphs (also known as finite dynamical systems) up to isomorphism.
  • JS-Sandpile : JavaScript implementation of the Abelian sandpile model.
    Click and play in your browser!
  • Secure Exchange Protocol (SXP) : An open, ubiquitous, peer-to-peer, secure protocol suite for multi-party exchanges of contracts.
  • qwgraph : An efficient python package for simulating quantum walks on graphs. Most of the package has been written in rust and compiled.


Credits

Site made with Jekyll from the template Hydeout and jekyll-scholar.
Runs on gitlab.lis-lab.fr/kevin.perrot/canawww with Gitlab pages.

Something wrong? Bug or obsolete info?
Please email Kevin Perrot at <name dot surname at lis-lab dot fr>. Thanks!