Computational complexity

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.

Researchers have shown that a problem relating to the energy of a quantum system is easy for quantum computers but hard for classical ones.

Integer linear programming can help find the answer to a variety of real-world problems. Now researchers have found a much faster way to do it.

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.

Artificial intelligence learned how to generate text and art better than ever before, while computer scientists developed algorithms that solved long-standing problems.

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

Mathematical proofs based on a technique called diagonalization can be relentlessly contrarian, but they help reveal the limits of algorithms.

How hard is it to prove that problems are hard to solve? Meta-complexity theorists have been asking questions like this for decades. A string of recent results has started to deliver answers.