check
HD-Combinatorics: Irit Dinur, "PCPs and high dimensional expansion" | Einstein Institute of Mathematics

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

Date: 
Mon, 27/11/201714:00-16:00
Location: 
Room 130, Feldman Building (IIAS), Givat Ram
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.