## Latest Articles

### Alan Turing and the Power of Negative Thinking

Mathematical proofs based on a technique called diagonalization can be relentlessly contrarian, but they help reveal the limits of algorithms.

### Complexity Theory’s 50-Year Journey to the Limits of Knowledge

How hard is it to prove that problems are hard to solve? Meta-complexity theorists have been asking questions like this for decades. A string of recent results has started to deliver answers.

### To Move Fast, Quantum Maze Solvers Must Forget the Past

Quantum algorithms can find their way out of mazes exponentially faster than classical ones, at the cost of forgetting the path they took. A new result suggests that the trade-off may be inevitable.

### How Randomness Improves Algorithms

Unpredictability can help computer scientists solve otherwise intractable problems.

### Bob Metcalfe, Ethernet Pioneer, Wins Turing Award

The American researcher was recognized for his central role in inventing, standardizing and commercializing the ubiquitous networking technology.

### In Neural Networks, Unbreakable Locks Can Hide Invisible Doors

Cryptographers have shown how perfect security can undermine machine learning models.

### The Computer Scientist Who Finds Life Lessons in Games

In Shang-Hua Teng’s work, theoretical and practical questions have long been intertwined. Now he’s turning his focus to the impractical.

### Finally, a Fast Algorithm for Shortest Paths on Negative Graphs

Researchers can now find the shortest route through a network nearly as fast as theoretically possible, even when some steps can cancel out others.

### New Algorithm Closes Quantum Supremacy Window

Random circuit sampling, a popular technique for showing the power of quantum computers, doesn’t scale up if errors go unchecked.