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

explainers

Alan Turing and the Power of Negative Thinking

By Ben Brubaker
September 5, 2023
Comment
Read Later

Mathematical proofs based on a technique called diagonalization can be relentlessly contrarian, but they help reveal the limits of algorithms.

computational complexity

Complexity Theory’s 50-Year Journey to the Limits of Knowledge

By Ben Brubaker
August 17, 2023
Comment
Read Later

How hard is it to prove that problems are hard to solve? Meta-complexity theorists have been asking questions like this for decades. A string of recent results has started to deliver answers.

Illustration of a lady walking through a hedge maze, with a man sweeping up her footprints.
quantum computing

To Move Fast, Quantum Maze Solvers Must Forget the Past

By Ben Brubaker
July 20, 2023
Comment
Read Later

Quantum algorithms can find their way out of mazes exponentially faster than classical ones, at the cost of forgetting the path they took. A new result suggests that the trade-off may be inevitable.

algorithms

How to Build a Big Prime Number

By Stephen Ornes
July 13, 2023
Comment
Read Later

A new algorithm brings together the advantages of randomness and deterministic processes to reliably construct large prime numbers.

An observer times birds flying between an apple tree and an orange tree that look like graphs.
computational complexity

Computer Scientists Inch Closer to Major Algorithmic Goal

By Kevin Hartnett
June 23, 2023
Comment
Read Later

A new paper finds a faster method for determining when two mathematical groups are the same.

geometry

Mathematicians Complete Quest to Build ‘Spherical Cubes’

By Jordana Cepelewicz
February 10, 2023
Comment
Read Later

Is it possible to fill space “cubically” with shapes that act like spheres? A proof at the intersection of geometry and theoretical computer science says yes.

Shang-Hua Teng in a blazer on a street
Q&A

The Computer Scientist Who Finds Life Lessons in Games

By Ben Brubaker
January 25, 2023
Comment
Read Later

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

Purple illustration of round qubits pointing to rows of blocks that progressively become more chaotic.
quantum computing

New Algorithm Closes Quantum Supremacy Window

By Ben Brubaker
January 9, 2023
Comment
Read Later

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

2022 in Review

The Year in Computer Science

By Bill Andrews
December 21, 2022
Comment
Read Later

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


Previous
  • 1
  • 2
  • 3
  • 4
  • ...
  • 5
Next
Follow Quanta
Facebook
Facebook

Twitter
Twitter

Youtube
YouTube

Instagram
Instagram

RSS
RSS

Newsletter

Past Month

Most Read Articles

This Data is Current Loading...
This Data is Current Loading...
This Data is Current Loading...
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

All Rights Reserved © 2023
An editorially independent publication supported by the Simons Foundation.