What's up in
computational complexity
Latest Articles
Graph Isomorphism Vanquished — Again
Just five days after posting a retraction, László Babai announced that he had fixed the error in his landmark graph isomorphism algorithm.
Complexity Theory Problem Strikes Back
The legendary graph isomorphism problem may be harder than a 2015 result seemed to suggest.
Landmark Algorithm Breaks 30-Year Impasse
Computer scientists are abuzz over a fast new algorithm for solving one of the central problems in the field.
Theorists Draw Closer to Perfect Coloring
A theorem for coloring a large class of “perfect” mathematical networks could ease the way for a long-sought general coloring proof.
A New Map Traces the Limits of Computation
A major advance in computational complexity reveals deep connections between the classes of problems that computers can — and can’t — possibly do.
A Grand Vision for the Impossible
Subhash Khot’s bold conjecture is helping mathematicians explore the precise limits of computation.
Computer Scientists Take Road Less Traveled
An infinitesimal advance in the traveling salesman problem breathes new life into the search for improved approximate solutions.