2016 : WHAT DO YOU CONSIDER THE MOST INTERESTING RECENT [SCIENTIFIC] NEWS? WHAT MAKES IT IMPORTANT?

The most interesting news came late in 2015—on November 10, to be precise, when László Babai of the University of Chicago announced that he had come up with a new algorithm for solving the graph-isomorphism problem. This algorithm appears to be much more efficient than the previous “best” algorithm, which has ruled for over thirty years. Since graph isomorphism is one of the great unsolved problems in computer science, if Babai’s claim stands up to the kind of intensive peer-review to which it will now be subjected then the implications are fascinating, not least because we may need to rethink our assumptions about what computers can and cannot do.

The graph isomorphism problem seems deceptively simple: how to tell when two different graphs (which is what mathematicians call networks) are really the same in the sense that there’s an “isomorphism”—a one-to-one correspondence between their nodes that preserves each node’s connections—between them. Easy to state, but difficult to solve, since even small graphs can be made to look very different just by moving their nodes around. The standard way to check for isomorphism is to consider all possible ways to match up the nodes in one network with those in the other. That’s tedious but feasible for very small graphs, but it rapidly gets out of hand as the number of nodes increases. To compare two graphs with just ten nodes, for example, you’d have to check over 3.6 million (i.e. 10 factorial) possible matchings. For graphs with 100 nodes you’re probably looking at a number bigger than all the molecules in the universe. And in a Facebook age, networks with millions of nodes are commonplace.

From the point of view of practical computing, factorials are really bad news because the running time of a factorial algorithm can quickly escalate into billions of years. So the only practical algorithms are those for problems whose solutions can be expressed as polynomials (e.g. n-squared or n-cubed, where n is the number of nodes) because running times for them increase much more slowly than those for factorial or exponential functions. 

The intriguing—tantalizing—thing about Babai’s algorithm is that it is neither pure factorial nor polynomial but what he calls “quasi-polynomial.” It’s not clear yet what this means, but the fuss in the mathematics and computer science community suggests that while the new algorithm might not be the Holy Grail, it is nevertheless significantly more efficient than what’s gone before.

If that turns out to be the case, what are the implications? Well, firstly, there may be some small but discrete benefits. Babai’s breakthrough could conceivably help with other kinds of computationally difficult problems. For example, in genomics researchers have been trying for years to find an efficient algorithm for comparing the long strings of chemical letters within DNA molecules. This is a problem analogous to that of graph isomorphism and any advance in that area may have benefits for genetic research.

But the most important implication of Babai’s work may be inspirational—in reawakening mathematicians’ interests in other kinds of hard problems that currently lie beyond the reach of even the most formidable computational resources. The classic example is the public-key encryption system on which the security of all online transactions depends. This works on asymmetry: it is relatively easy to take two huge prime numbers and multiply them together to produce an even larger number. But—provided the original primes are large enough—it is computationally difficult (in the sense that it would take an impracticable length of time) to factorize the product, i.e. determine the two original numbers from which it was calculated. If, however, an efficient factorizing algorithm were to be found, then our collective security would evaporate and we would need to go back to the drawing board.