Ben Brubaker

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

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.