What's up in

# computational complexity

## Latest Articles

### The Computer Scientist Who Finds Life Lessons in Games

In Shang-Hua Teng’s work, theoretical and practical questions have long been intertwined. Now he’s turning his focus to the impractical.

### New Algorithm Closes Quantum Supremacy Window

Random circuit sampling, a popular technique for showing the power of quantum computers, doesn’t scale up if errors go unchecked.

### The Year in Computer Science

Computer scientists this year learned how to transmit perfect secrets, why transformers seem so good at everything, and how to improve on decades-old algorithms (with a little help from AI).

### After a Quantum Clobbering, One Approach Survives Unscathed

A quantum approach to data analysis that relies on the study of shapes will likely remain an example of a quantum advantage — albeit for increasingly unlikely scenarios.

### How Do You Prove a Secret?

Zero-knowledge proofs allow researchers to prove their knowledge without divulging the knowledge itself.

### Computer Science Proof Unveils Unexpected Form of Entanglement

Three computer scientists have posted a proof of the NLTS conjecture, showing that systems of entangled particles can remain difficult to analyze even away from extremes.

### How Computer Scientists Learned to Reinvent the Proof

Why verify every line of a proof, when just a few checks will do?

### Computer Scientists Prove That Certain Problems Are Truly Hard

Finding out whether a question is too difficult to ever solve efficiently depends on figuring out just how hard it is. Researchers have now shown how to do that for a major class of problems.

### Which Computational Universe Do We Live In?

Cryptographers want to know which of five possible worlds we inhabit, which will reveal whether truly secure cryptography is even possible.