Ben Brubaker

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.

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.

Unpredictability can help computer scientists solve otherwise intractable problems.

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

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

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

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

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

Inspired by the results of a game-playing neural network, mathematicians have been making unexpected advances on an age-old math problem.