Randomness

When pigeons outnumber pigeonholes, some birds must double up. This obvious statement — and its inverse — have deep connections to many areas of math and computer science.

Randomness is essential to some research, but it’s always been prohibitively complicated. Now, we can use “pseudorandomness” instead.

Three researchers have figured out how to craft a proof that spreads out information while keeping it perfectly secret.

Across the social and biological sciences, statisticians use a technique that leverages randomness to deal with the unknown.

Computer scientist Lance Fortnow writes that by embracing the computations that surround us, we can begin to understand and tame our seemingly random world.

The prolific researcher found deep connections between randomness and computation and spent a career influencing cryptographers, complexity researchers and more.

Russell Impagliazzo studies hard problems, the limits of cryptography, the nature of randomness and more.

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.

Unpredictability can help computer scientists solve otherwise intractable problems.