What's up in

computational complexity

<p>Just five days after posting a retraction, László Babai announced that he had fixed the error in his landmark graph isomorphism algorithm.</p>
Abstractions blog

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.

<p>The legendary graph isomorphism problem may be harder than a 2015 result seemed to suggest.</p>
Abstractions blog

Complexity Theory Problem Strikes Back

The legendary graph isomorphism problem may be harder than a 2015 result seemed to suggest.

<p>Recent tests show that quantum computers made by D-Wave systems should solve some problems faster than ordinary computers. Researchers have begun to map out exactly which queries might benefit from these quantum machines.</p>
quantum computing

Computing’s Search for Quantum Questions

Recent tests show that quantum computers made by D-Wave systems should solve some problems faster than ordinary computers. Researchers have begun to map out exactly which queries might benefit from these quantum machines.

<p>Computer scientists are abuzz over a fast new algorithm for solving one of the central problems in the field.</p>
Computer Science

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.

<p>A theorem for coloring a large class of “perfect” mathematical networks could ease the way for a long-sought general coloring proof.</p>
Mathematics

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.

<p>A major advance in computational complexity reveals deep connections between the classes of problems that computers can — and can’t — possibly do.</p>
Computer Science

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.

<p>Subhash Khot’s bold conjecture is helping mathematicians explore the precise limits of computation.</p>
2014 Fields Medal and Nevanlinna Prize Winners

A Grand Vision for the Impossible

Subhash Khot’s bold conjecture is helping mathematicians explore the precise limits of computation.

<p>An infinitesimal advance in the traveling salesman problem breathes new life into the search for improved approximate solutions.</p>
traveling salesman problem

Computer Scientists Take Road Less Traveled

An infinitesimal advance in the traveling salesman problem breathes new life into the search for improved approximate solutions.