About

RESEARCH INTERESTS

I am fascinated with the behavior of certain dynamical systems where structures seem to spontaneously emerge and further grow in complexity over time. My goal is to use tools from mathematics and theoretical computer science to study such behaviour formally. In my research so far, I was interested in the following questions:

  • What formal properties of discrete systems correlate with our intuitive understanding of complexity and chaos?
  • How to automatically detect systems with complex behaviour?
  • How to formally measure what a given system can or cannot compute?

I mainly focused on studying cellular automata and derived new results about their dynamics and computational capacity using tools form statistical physics and universal algebra.

Publications

Recently Published Papers and Papers in Progress

We introduce a novel complexity metric which measures the asymptotic growth of the average computation time in cellular automata (CA). We use it to classify CA dynamics and to automatically search for CA with complex behavior.

PDF DOI talk

Generalization of the previous paper about classifying complex systems. We show the method works across various classes of discrete systems. We show the method indicates a region of systems at a phase transition and demonstrate that many hand-designed complex systems belong to this region.

accepted to ALife Journal

We study the computational capacity of elementary cellular automata (ECA) by measuring how many other ECA can they emulate. The results suggest that the most chaotic ECA are exactly those that cannot emulate any other. Thus, we propose a new definition of chaos in dynamical systems related to their computing power.

accepted to ALife 2021 Conference