What's up in

# computational complexity

## Latest Articles

### 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.

### Avi Wigderson, Complexity Theory Pioneer, Wins Turing Award

The prolific researcher found deep connections between randomness and computation and spent a career influencing cryptographers, complexity researchers and more.

### 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.

### Physicists Finally Find a Problem for Quantum Computers Alone

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

### Researchers Approach New Speed Limit for Seminal Problem

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.

### ‘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 Year in Computer Science

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

### 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.