Computational complexity

Mary Wootters discusses how error-correcting codes work, and how they are essential for reliable communication and storage.

In theory, quantum physics can bypass the hard mathematical problems at the root of modern encryption. A new proof shows how.

An attack on a fundamental proof technique reveals a glaring security issue for blockchains and other digital encryption schemes.

One computer scientist’s “stunning” proof is the first progress in 50 years on one of the most famous questions in computer science.

When pigeons outnumber pigeonholes, some birds must double up. This obvious statement — and its inverse — have deep connections to many areas of math and computer science.

Despite the hype, it’s been surprisingly challenging to find quantum algorithms that outperform classical ones. In this episode, Ewin Tang discusses her pioneering work in “dequantizing” quantum algorithms — and what it means for the future of quantum computing.

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.