News in Brief Computing

Retracted result on network equivalence reinstated

Solution to ‘graph isomorphism’ problem restored after error is found

two graphs

CONNECT THE DOTS  The graph isomorphism problem requires computers to quickly compare two graphs (shown) and determine if they are the same.

E. Otwell

By Emily Conover

- More than 2 years ago

A computer scientist has taken his colleagues on a rollercoaster ride.

In the span of several days, László Babai of the University of Chicago walked back his earlier claim of making a major advance on a classic puzzle of computer science, only to reinstate it after fixing an error in his work.