When Chaos Becomes Clarity: Abel Prize Winner Avi Wigderson Explores Power of Randomness

Randomness may seem like the opposite of order, but for mathematician Avi Wigderson, it is one of the most powerful forces shaping modern science. The 2021 Abel Prize laureate argues that chance is not only a feature of the natural world, but it is also a fundamental tool for understanding the world.

In his November 12 Stony Brook University lecture titled Randomness, Wigderson described how the study of unpredictability has revolutionized fields from computer science to physics. Speaking to the audience in the Della Pietra Family Auditorium at the Simons Center for Geometry and Physics, he invited the group to consider how randomness influences everything from the algorithms that secure digital communications to the questions surrounding mathematics.

Wigderson, the Herbert H. Maass Professor in the School of Mathematics at the Institute for Advanced Studyin Princeton, delivered the lecture as part of the Simons Center's Della Pietra Lecture Series. The lecture was the first of a series of three lectures that took place throughout the week.

"Randomness has fascinated humanity for millennia," Wigderson began. "It's been used to settle disputes, in gambling, in statistics, in science. The question is not only whether the universe is inherently deterministic or probabilistic, but whether we can tell the difference."

Wigderson described how randomness can be analyzed, measured and even generated. Using examples from computer science, mathematics, game theory and cryptography, he showed how random processes enable order, efficiency and security in the digital age.

One of the illustrations began with the toss of a coin. "Suppose I flip a coin 20 times," he said. "Which of these two sequences is more likely? The answer, of course, is that both are equally likely. These have probability of two to the power of 20. This is what we call the perfect randomness or uniform probability on sequences." That is at the center of how we define perfect randomness: the idea that each outcome has the same probability, regardless of pattern or appearance.

One of the illustrations began with the toss of a coin. "If I could flip a coin perfectly, heads has a 50 percent probability and tails has a 50 percent probability," he said. "Suppose I flip a coin 20 times. What sequence is more likely? The answer, of course, is that any sequence is equally likely, and has a probability of two to the power of 20, whether the sequence is 100 percent heads or 50 percent heads and 50 percent tails. This is what we call the perfect randomness or uniform probability on sequences."

That concept is at the center of how we define perfect randomness: the idea that each outcome has the same probability, regardless of pattern or appearance. The brain tends to perceive sequences with an even mix of heads and tails as "more likely" or "more random" than sequences with long streaks, but this is not a mathematical reality. In reality, the sequence of 20 heads has the same probability as any other specific sequence.

Wigderson then discussed how randomization has transformed modern computation. In fields ranging from physics to finance, randomized algorithms allow computers to solve problems that would be impossibly slow otherwise. "With randomness," he said, "we can make fast, approximate calculations where exact computation would take forever."

He cited examples like estimating the number of possible arrangements of molecules in a material, a calculation that once seemed impossible. "If you try to count every configuration deterministically," he said, "it would take longer than the age of the universe. But with random sampling, you can get an accurate answer quickly." Randomized methods, he added, also underpin essential systems like cryptography, which depend on unpredictable numbers to secure online communication and financial transactions.

Wigderson also addressed the limits of randomness. "Where do random bits come from?" he asked. "Some companies literally sell randomness, harvested from atmospheric noise or radioactive decay. But is that really random, and does it matter if it isn't perfect?"

To answer, he introduced the concept of pseudorandomness, deterministic processes that mimic the behavior of true randomness so effectively that even powerful computers cannot tell the difference. "Randomness," Wigderson said, "is in the eye of the beholder. What looks unpredictable to one observer might be predictable to another with more computational power. That means randomness isn't an absolute property of nature - it's relative to our ability to compute."

He demonstrated this with a thought experiment involving a coin toss. A person using only their eyes can't predict the outcome, but someone armed with high-speed cameras and a supercomputer could calculate the spin and trajectory well enough to know whether the coin will land heads or tails. "The experiment doesn't change," he said, "but the observer does. What's random to us is deterministic to someone with greater computational resources."

This shift in perspective, he explained, has redefined how mathematicians and computer scientists think about and approach probability. The study of pseudorandomness (objects or systems that appear random even when they aren't) has led to breakthroughs in error-correcting codes, data security, and the search for new mathematical truths.

Wigderson also addressed how randomness connects to efficiency and described how probabilistic algorithms can often be transformed into deterministic ones, given certain assumptions about computational hardness, known as the "hardness versus randomness" paradigm. "Every efficient randomized algorithm can, in theory, be simulated deterministically," he said, "if just one sufficiently hard problem exists." The result shows that randomness and computation are deeply intertwined.

"When we talk about pseudorandomness," he said, "we're really talking about creating order that looks like chaos. It's one of the few areas where mathematics allows us to imitate nature."

He emphasized that randomness is not the enemy of understanding, but is one of its most powerful tools. "Randomness lets us explore, approximate, and predict in ways that deterministic thinking alone cannot," he said. "Even in a world that may be deterministic at its core, the appearance of chance gives us new ways to make sense of it."

For those who would like to learn more about the topics discussed, Wigderson recommended his book on computational complexity, Mathematics and Computation: A Theory Revolutionizing Technology and Science, which offers an introduction to many of the ideas in the lecture and is available free of charge to download on his website. "It's written for anyone curious about how randomness and computation connect," he said.

- Beth Squire