1 July – Irit Dinur: P, NP, and Probabilistically Checkable Proofs
The P ≠ NP conjecture says that verifying is much easier than computing. The idea of checking a proof dates a long time back. The modern era has completely revolutionized this notion by injecting randomness and interaction into it. The past 3-4 decades of computational complexity have developed a beautiful theory, one of whose highlights is the PCP theorem. This theorem says that any NP question can be reformulated so that it has very robust proofs. So robust that they can be checked probabilistically by reading only a tiny random portion of the proof.
Dinur will talk about the PCP theorem and its many applications, and end by touching upon a surprising recent connection between PCPs and the so-called high-dimensional expanders, which are objects that come from pure math. The talk is also part of the Millennium Festival.
Irit Dveer Dinur is a full professor at the Weizmann Institute of Science. Her research is in the intersection of mathematics and theoretical computer science, with a particular focus on computational complexity and probabilistically checkable proofs. She was a plenary speaker at the 2010 ICM in Hyderabad, and has received several awards for her research including the Gödel Prize for her novel proof of the PCP theorem, the Erdős prize, and the ACM Paris Kanellakis Theory and Practice Award.
