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