A graph with six nodes, and three colors. (Source: Georgia Tech)One of the hardest things you can ask a computer to do is graph coloring.
If your instructions to the computer were in English, they might sound something like this: Start with a graph — a visual representation of a set of connected objects. Assign each object a color. If two objects are directly connected, they can’t share the same color. Now please color all the objects in the graph, using the smallest number of different colors.
With a sufficient number of connected objects (aka nodes), a problem like that might take some time for even the most advanced computer to solve. And we’re not talking about a few minutes. We’re talking weeks. Advanced though it may be, it still has to contend with a fundamental limitation: its binary brain.
Now, a team of researchers at Georgia Institute of Technology and University of Notre Dame has created a new computing system designed to address that. "We wanted to find a way to solve a problem without using the normal binary representations that have been the backbone of computing for decades," said Prof. Arijit Raychowdhury of Georgia Tech's School of Electrical and Computer Engineering.
"Applications today are demanding faster and faster computers to help solve challenges like resource allocation, machine learning and protein structure analysis — problems which at their core are closely related to graph coloring," Raychowdhury adds. "But for the most part, we've reached the limitations of modern digital computer processors.”
The researchers’ new system employs a network of electronic oscillators, and takes its cues from the human brain. The brain handles processing collectively, through a neural oscillatory network — rather than a central processor.
"It's the notion that there is tremendous power in collective computing," said Prof. Suman Datta of Notre Dame's College of Engineering, who is one of the study's co-authors.
When electrically connected via capacitive links, the oscillators, fabricated from vanadium dioxide, automatically synchronized to the same frequency. Oscillators directly connected to one another would operate at different phases within the same frequency, and those not directly connected would sync in both frequency and phase.
"If you suppose that each phase represents a different color, this system was essentially mimicking naturally the solution to a graph coloring problem," said Raychowdhury. "This opens up a new way of performative computation and constructing novel computational models. This is novel in that it's a physics-based computing approach, but it also presents tantalizing opportunities for building other customized analog systems for solving hard problems efficiently."
The system could be valuable for computations related to resource optimization. A power utility, for example, could use it to help maximize efficiency and usage of a vast electrical grid under certain constraints.
The next step would be building a larger network of oscillators able to solve graph coloring problems that incorporate more objects.
"Our goal is to reach a system with hundreds of oscillators, which would put us in striking distance of developing a computing substrate that could solve graph coloring problems whose optimal solutions are not yet known to mankind," added Datta.
