We care about your data, and we'd like to use cookies to give you a smooth browsing experience. Please agree and read more about our privacy policy.
Quanta Homepage
  • Physics
  • Mathematics
  • Biology
  • Computer Science
  • Topics
  • Archive

What's up in

computational complexity

Latest Articles

2020 in Review

The Year in Math and Computer Science

By Bill Andrews
December 23, 2020
Comment
Read Later

Even as mathematicians and computer scientists proved big results in computational complexity, number theory and geometry, computers proved themselves increasingly indispensable in mathematics.

An illustration of computer scientists looking down a new road that breaks open a traveling salesperson route.
algorithms

Computer Scientists Break Traveling Salesperson Record

By Erica Klarreich
October 8, 2020
Comment
Read Later

After 44 years, there’s finally a better way to find approximate solutions to the notoriously difficult traveling salesperson problem.

Animation showing multiple particles of light flowing together and leaving blue trails
Abstractions blog

Graced With Knowledge, Mathematicians Seek to Understand

By Kevin Hartnett
April 8, 2020
Comment
Read Later

A landmark proof in computer science has also solved an important problem called the Connes embedding conjecture. Mathematicians are working to understand it.

Animation showing toy-like depictions of computer science, quantum mechanics and pure math affecting each other.
computational complexity

Landmark Computer Science Proof Cascades Through Physics and Math

By Kevin Hartnett
March 4, 2020
Comment
Read Later

Computer scientists established a new boundary on computationally verifiable knowledge. In doing so, they solved major open problems in quantum mechanics and pure mathematics.

Art for "Computer Scientists Expand the Frontier of Verifiable Knowledge"
quantum information theory

Computer Scientists Expand the Frontier of Verifiable Knowledge

By Kevin Hartnett
May 23, 2019
Comment
Read Later

The universe of problems that a computer can check has grown. The researchers’ secret ingredient? Quantum entanglement.

Art for "Mathematicians Discover the Perfect Way to Multiply"
number theory

Mathematicians Discover the Perfect Way to Multiply

By Kevin Hartnett
April 11, 2019
Comment
Read Later

By chopping up large numbers into smaller ones, researchers have rewritten a fundamental mathematical speed limit.

Art for "In Quantum Games, There’s No Way to Play the Odds"
Abstractions blog

In Quantum Games, There’s No Way to Play the Odds

By Kevin Hartnett
April 1, 2019
Comment
Read Later

These games combine quantum entanglement, infinity and impossible-to-calculate winning probabilities. But if researchers can crack them, they’ll reveal deep mathematical secrets.

Art for "Major Quantum Computing Advance Made Obsolete by Teenager"
quantum computing

Major Quantum Computing Advance Made Obsolete by Teenager

By Kevin Hartnett
July 31, 2018
Comment
Read Later

18-year-old Ewin Tang has proven that classical computers can solve the “recommendation problem” nearly as fast as quantum computers. The result eliminates one of the best examples of quantum speedup.

Diagram showing show the hierarchy of different classes.
Abstractions blog

A Short Guide to Hard Problems

By Kevin Hartnett
July 16, 2018
Comment
Read Later

What’s easy for a computer to do, and what’s almost impossible? Those questions form the core of computational complexity. We present a map of the landscape.


Previous
  • 1
  • 2
  • 3
  • 4
  • 5
Next
The Quanta Newsletter

Get highlights of the most important news delivered to your email inbox

Recent newsletters
Quanta Homepage
Facebook
Twitter
Youtube
Instagram

  • About Quanta
  • Archive
  • Contact Us
  • Terms & Conditions
  • Privacy Policy
  • Simons Foundation
All Rights Reserved © 2023