Computational complexity

It’s been difficult to find important questions that quantum computers can answer faster than classical machines, but a new algorithm appears to do it for some critical optimization tasks.

Ten years ago, researchers proved that adding full memory can theoretically aid computation. They’re just now beginning to understand the implications.

Recent results show that large language models struggle with compositional tasks, suggesting a hard limit to their abilities.

Hypothetical devices that can quickly and accurately answer questions have become a powerful tool in computational complexity theory.

Three researchers have figured out how to craft a proof that spreads out information while keeping it perfectly secret.

Cryptography is the thread that connects Julius Caesar, World War II and quantum computing, and it now lies under nearly every part of modern life. In this week’s episode, computer scientist Boaz Barak and co-host Janna Levin discuss the past and future of secrecy.

Computational complexity theorists have discovered a surprising new way to understand what makes certain problems hard.

Researchers have proved that secure quantum encryption is possible in a world without hard problems.

Researchers have shown how to find the simplest description of a data set faster than by simply checking every possibility.