What's up in

# computational complexity

## Latest Articles

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

### Researchers Identify ‘Master Problem’ Underlying All Cryptography

The existence of secure cryptography depends on one of the oldest questions in computational complexity.

### Computer Scientists Eliminate Pesky Quantum Computations

For years, intermediate measurements made it hard to quantify the complexity of quantum algorithms. New work establishes that those measurements aren’t necessary after all.

### Surprising Limits Discovered in Quest for Optimal Solutions

Algorithms that zero in on solutions to optimization problems are the beating heart of machine reasoning. New results reveal surprising limits.