What's up in

# Computational complexity

## Latest Articles

### Computer Scientists Combine Two ‘Beautiful’ Proof Methods

Three researchers have figured out how to craft a proof that spreads out information while keeping it perfectly secret.

### How Does Math Keep Secrets?

Cryptography is the thread that connects Julius Caesar, World War II and quantum computing, and it now lies under nearly every part of modern life. In this week’s episode, computer scientist Boaz Barak and co-host Janna Levin discuss the past and future of secrecy.

### The Question of What’s Fair Illuminates the Question of What’s Hard

Computational complexity theorists have discovered a surprising new way to understand what makes certain problems hard.

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

### 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 That Only Quantum Computers Can Do

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