Dataset Information

Vertex coloring of graphs via phase dynamics of coupled oscillatory networks.

ABSTRACT: While Boolean logic has been the backbone of digital information processing, there exist classes of computationally hard problems wherein this paradigm is fundamentally inefficient. Vertex coloring of graphs, belonging to the class of combinatorial optimization, represents one such problem. It is well studied for its applications in data sciences, life sciences, social sciences and technology, and hence, motivates alternate, more efficient non-Boolean pathways towards its solution. Here we demonstrate a coupled relaxation oscillator based dynamical system that exploits insulator-metal transition in Vanadium Dioxide (VO₂) to efficiently solve vertex coloring of graphs. Pairwise coupled VO₂ oscillator circuits have been analyzed before for basic computing operations, but using complex networks of VO₂ oscillators, or any other oscillators, for more complex tasks have been challenging in theory as well as in experiments. The proposed VO₂ oscillator network harnesses the natural analogue between optimization problems and energy minimization processes in highly parallel, interconnected dynamical systems to approximate optimal coloring of graphs. We further indicate a fundamental connection between spectral properties of linear dynamical systems and spectral algorithms for graph coloring. Our work not only elucidates a physics-based computing approach but also presents tantalizing opportunities for building customized analog co-processors for solving hard problems efficiently.

SUBMITTER: Parihar A

PROVIDER: S-EPMC5430425 | biostudies-literature | 2017 Apr

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Vertex coloring of graphs via phase dynamics of coupled oscillatory networks.

Parihar Abhinav A Shukla Nikhil N Jerry Matthew M Datta Suman S Raychowdhury Arijit A

Scientific reports 20170419 1

While Boolean logic has been the backbone of digital information processing, there exist classes of computationally hard problems wherein this paradigm is fundamentally inefficient. Vertex coloring of graphs, belonging to the class of combinatorial optimization, represents one such problem. It is well studied for its applications in data sciences, life sciences, social sciences and technology, and hence, motivates alternate, more efficient non-Boolean pathways towards its solution. Here we demon ...[more]

PMID: 28424457

Similar Datasets

Project description:Macroscopic oscillations of different brain regions show multiple phase relationships that are persistent across time and have been implicated in routing information. While multiple cellular mechanisms influence the network oscillatory dynamics and structure the macroscopic firing motifs, one of the key questions is to identify the biophysical neuronal and synaptic properties that permit such motifs to arise. A second important issue is how the different neural activity coherence states determine the communication between the neural circuits. Here we analyse the emergence of phase-locking within bidirectionally delayed-coupled spiking circuits in which global gamma band oscillations arise from synaptic coupling among largely excitable neurons. We consider both the interneuronal (ING) and the pyramidal-interneuronal (PING) population gamma rhythms and the inter coupling targeting the pyramidal or the inhibitory neurons. Using a mean-field approach together with an exact reduction method, we reduce each spiking network to a low dimensional nonlinear system and derive the macroscopic phase resetting-curves (mPRCs) that determine how the phase of the global oscillation responds to incoming perturbations. This is made possible by the use of the quadratic integrate-and-fire model together with a Lorentzian distribution of the bias current. Depending on the type of gamma (PING vs. ING), we show that incoming excitatory inputs can either speed up the macroscopic oscillation (phase advance; type I PRC) or induce both a phase advance and a delay (type II PRC). From there we determine the structure of macroscopic coherence states (phase-locking) of two weakly synaptically-coupled networks. To do so we derive a phase equation for the coupled system which links the synaptic mechanisms to the coherence states of the system. We show that a synaptic transmission delay is a necessary condition for symmetry breaking, i.e. a non-symmetric phase lag between the macroscopic oscillations. This potentially provides an explanation to the experimentally observed variety of gamma phase-locking modes. Our analysis further shows that symmetry-broken coherence states can lead to a preferred direction of signal transfer between the oscillatory networks where this directionality also depends on the timing of the signal. Hence we suggest a causal theory for oscillatory modulation of functional connectivity between cortical circuits.

Dataset Information

Vertex coloring of graphs via phase dynamics of coupled oscillatory networks.

Publications

Vertex coloring of graphs via phase dynamics of coupled oscillatory networks.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets