What's up in
randomness
Latest Articles
Complexity Theory’s 50-Year Journey to the Limits of Knowledge
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.
How Randomness Improves Algorithms
Unpredictability can help computer scientists solve otherwise intractable problems.
How Do Mathematicians Know Their Proofs Are Correct?
What makes a proof stronger than a guess? What does evidence look like in the realm of mathematical abstraction? Hear the mathematician Melanie Matchett Wood explain how probability helps to guide number theorists toward certainty.
The Computer Scientist Who Parlays Failures Into Breakthroughs
Daniel Spielman solves important problems by thinking hard — about other questions.
Unimaginable Surfaces Discovered After Decades-Long Search
Using ideas borrowed from graph theory, two mathematicians have shown that extremely complex surfaces are easy to traverse.
Researchers Identify ‘Master Problem’ Underlying All Cryptography
The existence of secure cryptography depends on one of the oldest questions in computational complexity.
Mathematician Hurls Structure and Disorder Into Century-Old Problem
A new paper shows how to create longer disordered strings than mathematicians had thought possible, proving that a well-known recent conjecture is “spectacularly wrong.”
Researchers Defeat Randomness to Create Ideal Code
By carefully constructing a multidimensional and well-connected graph, a team of researchers has finally created a long-sought locally testable code that can immediately betray whether it’s been corrupted.
How and Why Computers Roll Loaded Dice
Researchers are one step closer to injecting probability into deterministic machines.