HD-Combinatorics: Irit Dinur, "PCPs and high dimensional expansion"

The "PCP theorem" says that problems in NP are hard in a robust or stable way.
I will give a brief intro to PCPs (and explain the acronym) and then try to outline a proof of the PCP theorem based on "agreement expansion" which is a form of high dimensional expansion.
My aim is to show how high dimensional expansion is inherently present in PCP type questions.


Mon, 27/11/2017 - 14:00 to 16:00


Room 130, Feldman Building (IIAS), Givat Ram