Biggest Breakthroughs in Computer Science: 2025

2025’s most surprising computational revelations included a new fundamental relationship between time and space, an undergraduate who overthrew a 40-year-old conjecture, and an important milestone in quantum computing.

00:00 FASTER HASH TABLES
Hash tables are fundamental ways to store data and are used in every computer. Since the 1970s, researchers have assumed that no improvements could be made to hash table design. Enter Andrew Krapivin who, while an undergraduate, invented a new kind of hash table, overturning a major conjecture and a long-held hypothesis about the limit to how fast hash tables could operate.

- Read more at Quanta Magazine: https://www.quantamagazine.org/undergraduate-upends-a-40-year-old-data-science-conjecture-20250210/
- Paper: "Optimal Bounds for Open Addressing Without Reordering" https://arxiv.org/abs/2501.02305

04:49 QUANTUM ERROR CORRECTION
Quantum computers have long tantalized researchers but a useful one has remained out of reach. This is because qubits, the fundamental computational units of quantum computing, are finicky and error-prone. Now a team at Google Quantum AI has shown that scaling up quantum error correction using an approach called the “surface code” can make these exotic machines possible.

- Read more at Quanta Magazine:
https://www.quantamagazine.org/quantum-computers-cross-critical-error-threshold-20241209/
- Paper: "Quantum error correction below the surface code threshold", https://www.nature.com/articles/s41586-024-08449-y

09:25 TIME VERSUS SPACE
To theoretical computer scientists, time and space (also known as memory) are the two fundamental resources of computation. Algorithms require a roughly proportional amount of space to runtime, and researchers long assumed there was no way to achieve anything better. In a stunner of a result, MIT researcher Ryan Williams found that memory is far more powerful than anyone had realized.

- Read more at Quanta Magazine: https://www.quantamagazine.org/for-algorithms-a-little-memory-outweighs-a-lot-of-time-20250521/
- Paper: "Simulating Time With Square-Root Space" https://arxiv.org/abs/2502.17779

---------
Quanta Magazine is an editorially independent publication supported by the Simons Foundation. We focus on developments in mathematics, theoretical physics, theoretical computer science and the basic life sciences.

READ free math and science articles on the Quanta website: www.quantamagazine.org

LEARN about the Simons Foundation: www.simonsfoundation.org

FOLLOW our social channels:
- Instagram: quantamag
- Bluesky: @quantamagazine.bsky.social‬
- Facebook: quantanews
- X: quantamagazine