What's up in

computational complexity

A graphic showing improvements in the speed of matrix multiplication
algorithms

Matrix Multiplication Inches Closer to Mythic Goal

March 23, 2021

A recent paper set the fastest record for multiplying two matrices. But it also marks the end of the line for a method researchers have relied on for decades to make improvements.

Abel Prize

Pioneers Linking Math and Computer Science Win the Abel Prize

March 17, 2021

Avi Wigderson and László Lovász won for their work developing complexity theory and graph theory, respectively, and for connecting the two fields.

algorithms

New Algorithm Breaks Speed Limit for Solving Linear Equations

March 8, 2021

By harnessing randomness, a new algorithm achieves a fundamentally novel — and faster — way of performing one of the most basic computations in math and computer science.

2020 in Review

The Year in Math and Computer Science

December 23, 2020

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

October 8, 2020

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

April 8, 2020

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

March 4, 2020

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

May 23, 2019

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

April 11, 2019

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