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.

Date: 

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

Location: 

Room 130, Feldman Building (IIAS), Givat Ram