Latest Articles
With Fifth Busy Beaver, Researchers Approach Computation’s Limits
After decades of uncertainty, a motley team of programmers has proved precisely how complicated simple computer programs can get.
Cryptographers Discover a New Foundation for Quantum Secrecy
Researchers have proved that secure quantum encryption is possible in a world without hard problems.
Cryptography Tricks Make a Hard Problem a Little Easier
Researchers have shown how to find the simplest description of a data set faster than by simply checking every possibility.
The Researcher Who Explores Computation by Conjuring New Worlds
Russell Impagliazzo studies hard problems, the limits of cryptography, the nature of randomness and more.
How Chain-of-Thought Reasoning Helps Neural Networks Compute
Large language models do better at solving problems when they show their work. Researchers are beginning to understand why.
Never-Repeating Tiles Can Safeguard Quantum Information
Two researchers have proved that Penrose tilings, famous patterns that never repeat, are mathematically equivalent to a kind of quantum error correction.
‘Magical’ Error Correction Scheme Proved Inherently Inefficient
Locally correctable codes need barely any information to fix errors, but they’re extremely long. Now we know that the simplest versions can’t get any shorter.
The ‘Accidental Activist’ Who Changed the Face of Mathematics
Throughout her 60-year career, Lenore Blum has developed new perspectives on logic and computation while championing women in mathematics and computer science. Now consciousness is on her mind.
An Easy-Sounding Problem Yields Numbers Too Big for Our Universe
Researchers prove that navigating certain systems of vectors is among the most complex computational problems.