What's up in

# computational complexity

## Latest Articles

### The Year in Math and Computer Science

Even as mathematicians and computer scientists proved big results in computational complexity, number theory and geometry, computers proved themselves increasingly indispensable in mathematics.

### Computer Scientists Break Traveling Salesperson Record

After 44 years, there’s finally a better way to find approximate solutions to the notoriously difficult traveling salesperson problem.

### Graced With Knowledge, Mathematicians Seek to Understand

A landmark proof in computer science has also solved an important problem called the Connes embedding conjecture. Mathematicians are working to understand it.

### Landmark Computer Science Proof Cascades Through Physics and Math

Computer scientists established a new boundary on computationally verifiable knowledge. In doing so, they solved major open problems in quantum mechanics and pure mathematics.

### Computer Scientists Expand the Frontier of Verifiable Knowledge

The universe of problems that a computer can check has grown. The researchers’ secret ingredient? Quantum entanglement.

### Mathematicians Discover the Perfect Way to Multiply

By chopping up large numbers into smaller ones, researchers have rewritten a fundamental mathematical speed limit.

### In Quantum Games, There’s No Way to Play the Odds

These games combine quantum entanglement, infinity and impossible-to-calculate winning probabilities. But if researchers can crack them, they’ll reveal deep mathematical secrets.

### Major Quantum Computing Advance Made Obsolete by Teenager

18-year-old Ewin Tang has proven that classical computers can solve the “recommendation problem” nearly as fast as quantum computers. The result eliminates one of the best examples of quantum speedup.

### A Short Guide to Hard Problems

What’s easy for a computer to do, and what’s almost impossible? Those questions form the core of computational complexity. We present a map of the landscape.