Local to global, high-dimensional expansion, and probabilistically checkable proofs
Sometimes you just don't have enough time to read an entire proof, a brief scan is all you can afford.
Probabilistically checkable proofs (PCPs), discovered 25 years ago, guarantee that even a brief scan will find an error if there is one. PCPs have a variety of implications, from hardness of computational optimization all the way to secure cloud computing.
A PCP proof is created by taking a normal proof and splitting it cleverly into fragments. The key is a theorem asserting that locally consistent fragments must be coming from a globally correct proof.
Recently, a connection was discovered between PCP “agreement tests” and a concept from combinatorial topology, so-called high-dimensional expanders. We will describe this connection and some future potential directions that it suggests.