##### Chaotic Cellular Neural/Nonlinear Networks for Solving Constraint Satisfaction

## Marie Curie International Incoming Fellowship: FP7-PEOPLE-IIF-299915

## Sponsored by the Research Executive Agency (REA)/European Commission

## Scientist in charge: Prof. Zoltán Néda

## Research Fellow: Dr. Mária Ercsey-Ravasz

### E-mail: ercsey.ravasz@phys.ubbcluj.ro

## Research topic:

Constraint satisfaction problems (such as Boolean satisfiability) constitute one of the hardest classes of optimization problems with many applications in technology and industry. In a recent paper the Fellow revealed a novel connection between these problems and chaotic dynamical systems. The paper provided an exact mapping of Boolean satisfiability (k-SAT) into a deterministic continuous-time dynamical system with a unique correspondence between its set of attractors and the k-SAT solutions. It was shown that optimization hardness is fundamentally equivalent to the phenomenon of chaos and turbulence: after a critical constraint density is reached, the trajectories become transiently chaotic before finding the solutions, signaling the appearance of optimization hardness. Numerical results have also shown that the presented dynamical system is very efficient in solving SAT problems. The system presented has the simplest possible form designed for fulfilling the mathematical requirements and is not yet suitable for direct implementation. However, the system is not necessarily unique. Using the same principles the goal of this project is to develop a deterministic continuous-time Cellular Neural/Nonlinear Network (CNN) model for solving constraint satisfaction. CNN models were already implemented in analog computers so this could result in a possible physical implementation of the model in the future, leading to numerous applications. The project will follow three major steps: 1) developing the CNN model and analyzing its mathematical properties. 2) Studying the efficiency of the CNN solver and properties of the transient chaotic behavior in hard problems. 3) Testing the robustness of the model to noise effects.

## Foreground publications during the project:

- B. Molnár, R. Sumi, M. Ercsey-Ravasz, "A CNN SAT-solver robust to noise", *CNNA2014 Proc. of the 14th IEEE Int. Conf. on Cellular Nanoscale Networks and their
Applications*, accepted, Notre Dame, IN, USA (2014)

- R. Sumi, B. Molnar, M. Ercsey-Ravasz, "Robust optimization with transiently chaotic dynamical systems", *EPL*, 2014, accepted.

- N.T. Markov, M. Ercsey-Ravasz, D.C. Van Essen, K. Knoblauch, Z. Toroczkai, H. Kennedy, "Cortical High-density Counter-stream Architectures", *Science*, **342**, 1238406, 2013 doi:10.1126/science.1238406

- M. Ercsey-Ravasz, N.T. Markov, C. Lamy, D.C. Van Essen, K. Knoblauch, Z. Toroczkai, H. Kennedy, "A predictive network model of cerebral cortical connectivity based on a distance rule", *Neuron*, **80**, 184, 2013 doi:10.1016/j.neuron.2013.07.036

- B. Molnár, M. Ercsey-Ravasz, "Asymmetric Continuous-Time Neural Networks without Local Traps for Solving Constraint Satisfaction Problems". PLoS ONE 8(9): e73400, 2013. doi:10.1371/journal.pone.0073400

- N.T. Markov, M. Ercsey-Ravasz, C. Lamy, A.R. Ribeiro Gomes, L. Magrou, P. Misery, P. Giroud, P. Barone, C. Dehay, Z. Toroczkai, K. Knoblauch, D.C. Van Essen, H. Kennedy. "The role of long-range connections on the specificity of the macaque interareal cortical network" * PNAS * ** 110**, 5187 (2013), doi:10.1073/pnas.1218972110

- B. Molnár, Z. Toroczkai, M. Ercsey-Ravasz, "Continuous-time Neural Networks Without Local Traps for Solving Boolean Satisfiability", *CNNA2012 Proc. of the 13th IEEE Int. Conf. on Cellular Nanoscale Networks and their
Applications*, p. 4012, Torino, Italy (2012) doi:10.1109/CNNA.2012.6331411

- M. Ercsey-Ravasz, Z. Toroczkai, "Dontesek fizikaja es rejtvenyek kaosza" ("Physics of decision making and chaos of puzzles") in * A fizika, matematika es muveszet talalkozasa az oktatasban, kutatasban (Physics, mathematics and arts in education and research)*, Ed.: A. Juhasz, T. Tel, Publisher: Science Department of the Eotvos Lorand University, Hungary, 2013.

## Background publications relevant to the project:

- M. Ercsey-Ravasz, Z. Toroczkai, "The Chaos Within Sudoku", *Nature Scientific Reports* **2**, 755 (2012) doi:10.1038/srep00725

- M. Ercsey-Ravasz, Z. Toroczkai, "Optimization Hardness as Transient Chaos in an Analog Approach to Constraint Satisfaction", *Nature Physics* **7**, 966 (2011) arxiv:1208.0526

- N. T. Markov, M. Ercsey-Ravasz, A.R. Ribiero Gomes, C. Lamy, J. Vezoli, L. Magrou, P. Misery, A. Falchier, R. Quilodran, J. Sallet, M.A. Gariel, R. Gamanut, C. Huissoud, S. Clavagnier, P. Giroud, D. Sappey-Marinier, P. Barone, C. Dehay, Z. Toroczkai, K. Knoblauch, D.C. Van Essen, H. Kennedy. "A weighted and directed interareal connectivity matrix for macaque cerebral cortex" *Cerebral Cortex* , advance access , Sep. 25 (2012)

- M. Ercsey-Ravasz, Z. Neda, T. Roska, "Stochastic optimization of spin-glasses on cellular neural/nonlinear network based processors", * Physica A * ** 388 **, 1024 (2009) doi:10.1016/j.physa.2008.11.037

- M. Ercsey-Ravasz, Z. Neda, T. Roska, "Cellular Neural Networks for NP-Hard Optimization", * EURASIP J. on Advances in Signal Processing *, 646975 (2009) 10.1155/2009/646975

## Full list of publications can be found here.

## Conferences, Workshops, Invited seminars:

- M. Ercsey-Ravasz “Analog approaches to hard optimization: from Sudoku to CNNs”, *Statistical Mechanics of Unsatisfiability and Glasses*, Mariehamn, Finland, 23-26 May, 2012

- M. Ercsey-Ravasz "Döntések fizikája és rejtvények káosza" ("Physics of decisions and chaos of puzzles"), * A fizika, matematika és művészet találkozása az oktatásban (Physics, mathematics and arts in high school) * Tg. Mures, Romania, August 15, 2012

- M. Ercsey-Ravasz “Solving constraint satisfaction problems via transiently chaotic analog systems and CNN dynamics”, *CNNA 2012*, Torino, Italy (2012)

- B. Molnár, Z. Toroczkai. M. Ercsey-Ravasz, "Continuous-time Neural Networks Without Local Traps for Solving Boolean Satisfiability", *CNNA 2012*, Torino, Italy (2012)

- The fellow visited her collaborator Prof. Zoltan Toroczkai at the University of Notre Dame, IN, USA in Oct. 2012.

- M. Ercsey-Ravasz "Asymmetric neural networks for solving constraint satisfaction", invited seminar at the Information Technology Department of the Pazmany Peter Catholic University, Hungary,22 February, 2013

- M. Ercsey-Ravasz, "The highly connected brain", invited seminar, Harvard Medical School, Beth Israel Deaconess Medical Center, Boston, USA, 29 October 2013

- The fellow visited her collaborator Prof. Tamas Roska at the Information Technology Department of the Pazmany Peter Catholic University, Budapest, Hungary, Oct. 1-2, 2013.

- The fellow visited her collaborator Prof. Zoltan Toroczkai at the University of Notre Dame, IN, USA in Oct. 2013.

- A.R. Gamanut, R.B. Gamanut, A. Burkhalter, D. van Essen, M. Ercsey-Ravasz, Z. toroczkai, K. Knoblauch, H. Kennedy, "Correlations between brain size and network properties of the cortex", poster at the IPSEN conference *Micro-, meso- and macro-connectomics of the brain*, Paris, May 5, 2014.

- She participated at the IPSEN conference *Micro-, meso- and macro-connectomics of the brain*, Paris, May 5, 2014, where her neuroscientist collaborator Dr. Henry Kennedy gave a talk about their common work, this will also result in a book chapter with title "The Brain in Space", to appear at the end of 2014.

The fellow visited her collaborators Dr. Henry Kennedy and K. Knoblauch at the INSERM institute in Lyon, May 6-9, 2014.

## Dissemination activities preformed by the fellow:

-the fellow gave a talk at a conference organized for highschool teachers in Transylvania: "Döntések fizikája és rejtvények káosza" ("Physics of decisions and chaos of puzzles"), * A fizika, matematika és művészet találkozása az oktatásban (Physics, mathematics and arts in high school) * Tg. Mures, Romania, August 15, 2012. She also wrote an article with the same title in the proceedings of this conference, which will reach highschool teachers from all over Trasylvania.

-She participated on the conference "Vandoregyetem" organized for college students, October 2012.

-She was invited to the Unitarian Highschool Janos Zsigmond, where she gave a talk with title "This Is All Physics", May 2013.

-She has given disseminating talks to the highschool students who participated on the Vermes Miklos Physics Competition, 2013.

-She gave a talk with title "Kaosz a Sudokuban" ("The Chaos within Sudoku"), for high-school students at the Transylvanian Scientific Conference for Students.

-She gave a talk at the opening ceremony of the 2013/2014 school year at the Faculty of Physics, Babes-Bolyai University.

-She prepared a high-school student for the National Physics Olympics, 2014

## The heavily connected brain - Cortical high-density counterstream architectures

**Background.**The cerebral cortex is divisible into many individual areas, each exhibiting distinct connectivity profiles, architecture, and physiological characteristics. Interactions among cortical areas underlie higher sensory, motor, and cognitive functions. Graph theory provides an important framework for understanding network properties of the interareal weighted and directed connectivity matrix reported in recent studies.Density and topology of the cortical graph. **Figure** (Left) The 66% density of the cortical matrix (black triangle) is considerably greater than in previous reports (colored points) and is inconsistent with a small-world network. (Right) A bow-tie representation of the high-density cortical matrix. The high-efficiency cortical core has defined relations with the cortical periphery in the two fans.
**Advances.** We derive an exponential distance rule that predicts many binary and weighted features of the cortical network, including efficiency of information transfer, the high specificity of long-distance compared to short-distance connections, wire length minimization, and the existence of a highly interconnected cortical core. We propose a bow-tie representation of the cortex, which combines these features with hierarchical processing.
**Outlook.** The exponential distance rule has important implications for understanding scaling properties of the cortex and developing future large-scale dynamic models of the cortex.

- N.T. Markov, M. Ercsey-Ravasz, D.C. Van Essen, K. Knoblauch, Z. Toroczkai, H. Kennedy, "Cortical High-density Counter-stream Architectures", *Science*, **342**, 1238406, 2013 doi:10.1126/science.1238406

## The Exponential Distance Rule of the Brain

Recent advances in neuroscience have engendered interest in large-scale brain networks. Using a consistent database of cortico-cortical connectivity, generated from hemisphere-wide, retrograde tracing experiments in the macaque, we analyzed interareal weights and distances to reveal an important organizational principle of brain connectivity. Using appropriate graph theoretical measures, we show that although very dense (66%), the interareal network has strong structural specificity. Connection weights exhibit a heavy-tailed lognormal distribution spanning five orders of magnitude and conform to a distance rule reflecting exponential decay with interareal separation. A single-parameter random graph model based on this rule predicts numerous features of the cortical network: (1) the existence of a network core and the distribution of cliques, (2) global and local binary properties, (3) global and local weight-based communication efficiencies modeled as network conductance, and (4) overall wire-length minimization. These findings underscore the importance of distance and weight-based heterogeneity in cortical architecture and processing.

- M. Ercsey-Ravasz, N.T. Markov, C. Lamy, D.C. Van Essen, K. Knoblauch, Z. Toroczkai, H. Kennedy, "A predictive network model of cerebral cortical connectivity based on a distance rule", *Neuron*, **80**, 184, 2013 doi:10.1016/j.neuron.2013.07.036

## Asymmetric CNN without local traps for solving SAT problems

We present a deterministic continuous-time recurrent neural network similar to CNN models, which can solve Boolean satisfiability ($k$-SAT) problems without getting trapped in non-solution fixed points. The model can be implemented by analog circuits, in which case the algorithm would take a single operation: the template (connection weights) is set by the $k$-SAT instance and starting from any initial condition the system converges to a solution. We prove that there is a one-to-one correspondence between the stable fixed points of the model and the $k$-SAT solutions and present numerical evidence that limit cycles may also be avoided by appropriately choosing the parameters of the model.

- B. Molnár, Z. Toroczkai, M. Ercsey-Ravasz, *CNNA2012 Proc. of the 13th IEEE Int. Conf. on Cellular Nanoscale Networks and their
Applications*, Torino, Italy (2012) doi:10.1109/CNNA.2012.6331411

## The Chaos Within Sudoku

The mathematical structure of Sudoku puzzles is akin to hard constraint satisfaction problems lying at the basis of many applications, including protein folding and the ground-state problem of glassy spin systems. Via an exact mapping of Sudoku into a deterministic, continuous-time dynamical system, here we show that the difficulty of Sudoku translates into transient chaotic behavior exhibited by this system. We also show that the escape rate κ, an invariant of transient chaos, provides a scalar measure of the puzzle’s hardness that correlates well with human difficulty ratings. Accordingly, η=-log_{10} (κ) can be used to define a ‘‘Richter’’-type scale for puzzle hardness, with easy puzzles having 0 < η ≤ 1, medium ones 1 < η ≤ 2, hard with 2 < η ≤ 3 and ultra-hard with η > 3. To our best knowledge, there are no known puzzles with η > 4.

M. Ercsey-Ravasz, Z. Toroczkai, *Scientific Reports* **2**, 755 (2012) doi:10.1038/srep00725

Echoes in media: Huffington Post , Daily Mail , Technology review , CBS news , Income Magazine , Antena 3

Also see simulation movie on youtube## Turbulent Computation

Boolean satisfiability (k-SAT) is one of the most studied optimization problems, as an efficient (that is, polynomial-time) solution to k-SAT (for k > 2) implies efficient solutions to a large number of hard optimization problems. Here we propose a mapping of k-SAT into a deterministic continuous-time dynamical system with a unique correspondence between its attractors and the k-SAT solution clusters. We show that beyond a constraint density threshold, the analog trajectories become transiently chaotic, and the boundaries between the basins of attraction of the solution clusters become fractal, signalling the appearance of optimization hardness. Analytical arguments and simulations indicate that the system always finds solutions for satisfiable formulae even in the frozen regimes of random 3-SAT and of locked occupation problems (considered among the hardest algorithmic benchmarks), a property partly due to the system's hyperbolic character. The system finds solutions in polynomial continuous time, however, at the expense of exponential fluctuations in its energy function.

M. Ercsey-Ravasz, Z. Toroczkai, *Nature Physics* **7**, 966 (2011) doi:10.1038/nphys2105 , arxiv:1208.0526

Echoes in media: Notre Dame News

## Research fellow

### Dr. Mária Ercsey-Ravasz

After obtaining Ph.D. in Physics and Information Technology, Dr. Ercsey-Ravasz have spent 3 years as a postdoctoral researcher at the University of Notre Dame, IN, USA. She returned to Romania to the Babes-Bolyai University in September 2011. She has started this Marie Curie Fellowship in May 2012.

homepage, CV , Publications