2017
Nov
27

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

2:00pm to 4:00pm

## 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.