complexity

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.

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.

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

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

Syukuro Manabe and Klaus Hasselmann have been honored for their work that led to reliable predictions of the effects of climate change. They will share the Nobel with Giorgio Parisi, who has made pioneering studies of chaotic physical systems.

While the study of the SARS-CoV-2 virus was the most urgent priority, biologists also learned more about how brains process information, how to define individuality and why sleep deprivation kills.

To tame urban traffic, the computer scientist Carlos Gershenson finds that letting transportation systems adapt and self-organize often works better than trying to predict and control them.

Skyrocketing animal diversity a half-billion years ago was linked to spikes and dips in marine oxygen levels, according to a detailed geological study.

As researchers delve deeper into the behavior of decentralized collective systems, they’re beginning to question some of their initial assumptions.