Finding Beauty and Meaning in Computational Complexity

For the first time in its 95-year history, the Institute for Advanced Study (IAS) in Princeton, NJ, has appointed a woman as a permanent professor in its School of Mathematics. Last summer, computer scientist Irit Dinur joined the research-only IAS, a major center for computer science and discrete mathematics, on leave from the Weizmann Institute of Science in Israel.

A leading figure in computational complexity theory, Dinur has received several honors, including two from ACM: the 2022 Kanellakis Theory and Practice Award, and the 2019 Gödel Prize (awarded jointly by ACM and the European Association for Theoretical Computer Science). She is known for “uncovering deep and unexpected connections between different areas of mathematics and computer science,” according to Shmuel Safra, a professor of computer science at Israel’s Tel Aviv University. 

Born in Jerusalem, Israel, in 1973, Dinur gravitated to mathematics and computer science as a student at Tel Aviv University. But it was only towards the end of her undergraduate study that she found a true intellectual home for herself, when she took a course on computational complexity theory.

The subject “combined lovely math with really beautiful questions that have a philosophical nature,” she said, questions like, What is randomness?, and What does it mean for problems to be hard or easy? Using mathematical tools to talk about such questions was for her “so exciting and moving,” she said. “Math is beautiful and we can enjoy it for beauty’s sake, but here was something that was even beyond beauty; it was like actual meaning in our life. I thought that was a fascinating combination.”

When she became a graduate student at Tel Aviv University, Dinur took up a central theme in computational complexity, namely, hardness of approximation. Her Ph.D. thesis investigated the vertex cover problem, a combinatorial question appearing in the famous 1972 paper by Richard Karp that led to the birth of complexity theory. Dinur showed that not only is the vertex cover problem hard to solve, but finding even an approximate solution is hard.

Most Ph.D. students “tend to avoid such daunting research questions due to the high risk and uncertain payoff, but Irit approached this challenge with extraordinary resilience,” said Safra, who advised her doctoral thesis and collaborated extensively with her afterward. Dinur introduced new methodologies that “have since become invaluable tools,” he said. Her breakthrough work not only advanced the field, he noted, but also contributed to the development of the Unique Games Conjecture, a major open question that has spawned much research.

Dinur’s thesis paved the way for her most famous work, her 2006 proof of the PCP theorem, which Boaz Barak, a professor of computer science at Harvard University, described as a prime example of the “originality and creativity [that] shine through in many of her works.” PCP stands for “probabilistically checkable proofs,” a counter-intuitive notion that exemplifies the mysterious interplay between randomness and computation.

Traditionally, a mathematician produces a proof of a theorem by writing down a series of logical steps that establish the theorem’s truth. Verifying that the proof is correct means checking every single step. If the proof is lengthy, the checking process could take a long time. What if someone told you that you could verify the proof by checking just a few randomly chosen steps? “That seems to be completely ridiculous,” said Dinur, “but it turns out that there are special formats for writing proofs that are very resilient to errors.”

These formats are called PCPs. If you rewrite a traditional proof in PCP format, any errors in the proof are amplified in such a way that checking just a few randomly chosen steps in the PCP will tell you, with high probability, whether the original proof was correct. What’s more, the number of steps to be checked in the PCP is independent of the length of the proof.

The first indication that PCPs might exist came from research in the early 1990s that suggested PCPs would have a deep connection to hardness of approximation problems, like the one Dinur treated in her doctoral thesis. In the late 1990s, work by several people, Safra included, culminated in a proof of the PCP theorem, which established the existence of PCPs.

That work developed abstract technical machinery that today is well understood, but at the time struck many, Dinur included, as rather opaque. “It felt like a bunch of magic,” she recalled. She knew that machinery inside and out and even wrote papers about how to modify some parts of it, but she was still not satisfied. Seeking a deeper understanding of the PCP phenomenon, she set about developing a more conceptual, geometric approach, making novel use of what are known as expander graphs. She came up with a completely new, far simpler proof of the PCP theorem.

Dinur’s new proof was a surprise. “The original proof was considered impenetrable by many, and few expected that a completely different, combinatorial approach was possible,” said Safra. In particular, Dinur’s use of expander graphs connected the PCP theorem to broader concepts in mathematics, bringing a perspective “that has had a lasting impact, inspiring further research into the connections between PCPs and other mathematical areas,” said Safra.

Barak sees Dinur’s “persistence in getting to the bottom of phenomena” in another strand of her research, on local testing of codes. Just as PCPs provide a way to verify a proof by checking just a few steps, locally testable codes provide a way to verify that a data string is a codeword by checking just a few bits in the string. “By focusing on resolving some of the deep questions in the field, she uncovered new connections and beautiful structures that could not have been foreseen,” said Barak.

Dinur’s latest work has centered on high-dimensional versions of expander graphs. “I view this as a way to enlarge the playground in which PCP theorems can exist,” she said. “High-dimensional expansion gives a completely new perspective and new understanding of older things, which is something I always enjoy. I enjoy listening to things again and again, understanding them better and better. Maybe other people could be bored by that, but things that I already find fascinating, I usually don’t lose interest in them.”

When the IAS School of Mathematics was founded in 1933, women faced significant barriers to entering science and mathematics. Today, as those barriers continue to fall, Dinur’s appointment as the school’s first woman professor is at once historic and unremarkable. 

For her part, Dinur has found participation in theoretical computer science to be essentially barrier-free. “My field is very receptive and accepting,” she said. “It’s kind of easy to thrive here.” She recalled a time when, as a senior faculty member, she became aware of a case of sexual harassment. “I knew that I could approach a bunch of my male friends and that they would be very supportive, and they were,” she said. “The atmosphere in my field is very good. That’s more important than if you are a woman or a man.”

Allyn Jackson is a journalist specializing in science and mathematics, who is based in Germany.