The Many Worlds of Computational Complexity: A Conversation with Russell Impagliazzo

Thursday - March 28 2024, 00:18 UTC - 1 year ago

Russell Impagliazzo is a leading researcher in computational complexity, with a lifelong interest in math and a love for tabletop role-playing games and improv comedy. He has made significant contributions to the P versus NP problem and the understanding of randomness in computation. His 1995 paper on different possible worlds has inspired much research in meta-complexity. In this interview, he discusses his work and the playful spirit that guides it.

As you venture into the world of computational complexity, you are bombarded with a dizzying array of symbols and concepts - BPP, AC0[m], Σ2P, YACC, and many others. It can be overwhelming - where to begin? Fortunately, the eminent researcher Russell Impagliazzo has been at the forefront of this field for four decades, cutting through the complexity like a seasoned explorer. One of the most famous questions in computational complexity is the P versus NP problem .

It asks whether seemingly difficult problems can actually be solved easily, given the right algorithm. Such an answer would have far-reaching implications, from advancing scientific understanding to revolutionizing modern cryptography. Impagliazzo has played a pivotal role in unifying the theoretical foundations of cryptography in the 1980s and 1990s. In a groundbreaking paper in 1995, he introduced the concept of five hypothetical worlds that could help us understand P versus NP and related problems .

These worlds - Algorithmica, Heuristica, Pessiland, Minicrypt, and Cryptomania - have become a popular framework for exploring meta-complexity. But Impagliazzo is not just a serious academic; he brings a playful spirit to his work. As a lifelong fan of tabletop role-playing games like Dungeons and Dragons, he has a talent for creating new worlds and rules to guide his explorations. He also finds inspiration in improvisational comedy, using its principles to enhance his mathematical thinking .

Beyond P versus NP, Impagliazzo's work on randomness in computation has been groundbreaking. In the late 1970s, it was shown that randomness can actually improve algorithms for solving inherently deterministic problems - a counterintuitive finding that puzzled researchers for years. Together with Avi Wigderson and other collaborators, Impagliazzo showed that it is possible to convert randomized algorithms into deterministic ones, and vice versa .

This work provided crucial insights into the role of randomness in solving difficult problems. Quanta had the opportunity to speak with Impagliazzo about his fascinating career. In this interview, he shares his thoughts on different worlds, consulting oracles, and how his love for improv comedy has influenced his mathematical thinking. This conversation has been edited and condensed for clarity.