By Josh Baxt and Katie E. Ismael
Russell Impagliazzo, a longtime professor in UC San Diego’s Department of Computer Science and Engineering, is immersed in computational complexity, identifying how difficult it will be to solve specific problems on fast computers. On the side, he immerses himself in improv comedy, a completely different form of complexity.
The computer scientist turned comedian who joined CSE in 1991 will be celebrated with a workshop on “Wrestling Complexity and the Five-Worlds Conundrum” on May 12 and 13, which happens to coincide with his 60th birthday.
"Wrestling with Complexity and the Five-Worlds Conundrum" will cover topics in theoretical computer science focusing on the central open problems in the hardness of computation, cryptography, and the complexity of proofs. The "Five-Worlds Conundrum” refers to Impagliazzo's formulation of the five main possible ways in which questions about computability and cryptography may eventually be resolved. Workshop information and registration is available at wcw.ucsd.edu.
The workshop will include a short improv show by Impagliazzo and others.
On Complexity and Cryptography
On the computational side, Impagliazzo points to the gap between multiplication and factoring. Multiplying two numbers is easy, grade school stuff. Computers take it to the next level, multiplying hundred- or even thousand-digit numbers. But still, it’s a relatively low-complexity problem.
On the other hand, factoring, which seeks to reverse the process, is incredibly challenging. There are no efficient ways to deduce which numbers were multiplied together to get that final tally. But in this case, complexity is incredibly useful.
“If someone came up with a fast algorithm to find factors and reverse simple multiplication it would break RSA encryption algorithm,” said Impagliazzo. “All our online credit card transactions would be vulnerable.”
Complexity can be our friend, but someone has to recognize and understand it. That’s Impagliazzo’s role, figuring out how difficult it will be to solve certain problems, and he’s in good company at CSE.
“UC San Diego is at the forefront of an area called fine-grain complexity theory,” said Impagliazzo, “where we try to give exact or very close quantitative bounds on the likely difficulty of these computational problems.”
Impagliazzo does a lot of work in cryptography, an area that prizes asymmetrical complexity. The problem needs to be easy for some people but virtually impossible for everyone else.
“Cryptography needs problems that are easy to generate solutions, but if some random person were given the puzzle, they couldn’t find the solution,” said Impagliazzo. “We come up with all these reasons why problems might be hard. Most people are upset about it because they don’t want to know the problems they’re trying to solve are super hard – but cryptographers get really happy.”
Impagliazzo first made his mark on the field in 1995, when he published the influential A Personal View of Average-Case Complexity (known as the “five worlds” paper), in which he describes five possible worlds – Algorithmica, Heuristica, Pessiland, Minicrypt and Cryptomania – and their implications to computer science.
“I sketched out five possible answers to open problems in complexity theory and how they would impact the world,” said Impagliazzo. “Each of these five possible answers gave a descriptive view of the world that would be created if that particular answer were true.”
The Challenges of Comedy
When Impagliazzo first arrived in San Diego, he was a stranger in a new town and quickly set up an algorithm to find new friends outside work.
“I decided I needed a hobby,” he said, “so I looked in the San Diego Reader and started crossing out things I didn't want to do. That eventually left me with improv comedy. I didn't really think of myself as a funny person, but I had friends who had tried improv, and they weren't funny either, so I decided to give it a shot.”
Comedy helped him grow a different part of his brain. As a scientist, he was trained to think carefully and never say anything that might be misleading or, even worse, completely untrue. In improv, these things are encouraged.
It took some time, but eventually Impagliazzo started to get it. When he began in comedy, one friend in class thought he was the most painfully shy person she had ever met. Two years later, she saw a different person.
“There’s a game where we have to tell a continuous story, someone would start and then others would pick it up. If you messed up the story, you had to die in an interesting way,” recalled Impagliazzo. “So, this one time, I was the last person standing, and my reward was to tell the moral of the story standing on one foot, which I did. She was really impressed, and now we’re married.”