Ben Brubaker

After decades of uncertainty, a motley team of programmers has proved precisely how complicated simple computer programs can get.

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.

Russell Impagliazzo studies hard problems, the limits of cryptography, the nature of randomness and more.

Large language models do better at solving problems when they show their work. Researchers are beginning to understand why.

Two researchers have proved that Penrose tilings, famous patterns that never repeat, are mathematically equivalent to a kind of quantum error correction.

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.

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.

Researchers prove that navigating certain systems of vectors is among the most complex computational problems.