Irit Dinur

Irit Dinur is an Israeli computer scientist. She is professor of computer science at the Weizmann Institute of Science. In 2024 she was appointed a permanent faculty member in the School of Mathematics of the Institute for Advanced Study. Her research is in foundations of computer science and in combinatorics, and especially in probabilistically checkable proofs and hardness of approximation.

Early life and education Irit Dinur was born in Jerusalem in 1973. She studied computer science and math at Tel Aviv University. A course on computational complexity theory sparked her research interest through its combination of math and philosophy.

Dinur earned her doctorate in 2002 from the school of computer science at Tel Aviv University, advised by Shmuel Safra. In it, Dinur tackled the vertex cover problem, which had been proposed in Richard Karp's seminal 1972 paper on complexity theory. She showed that the vertex cover problem, and its approximate solution, are hard to solve. The techniques she developed for her proofs have since inspired the open question of the Unique Games Conjecture. From 2007 to 2024, Dinur was a professor at the Weizmann Institute. The PCP theorem, concerning probabilistically checkable proofs, states that some mathematical proofs can be checked with a high success rate just by writing them in PCP form and then randomly checking whether a few steps are true. Dinur creatively used expander graphs to prove the theorem via geometric means, and this connected the intuition behind the PCP theorem to other fields of math. She was a plenary speaker at the 2010 International Congress of Mathematicians. In 2012, she won the Anna and Lajos Erdős Prize in Mathematics, given by the Israel Mathematical Union. She was the William Bentinck-Smith Fellow at Harvard University in 2012–2013. In 2019, she won the Gödel Prize for her paper "The PCP theorem by gap amplification".