The study of Probabilistically Checkable Proofs, starting with the discovery of the PCP Theorem, is a cornerstone of modern computer science, with impact on complexity theory, algorithms, and cryptography. Born as a purely theoretical notion, mostly used to prove hardness of approximation results, PCPs are now becoming a widely deployed tool in blockchain platforms. The workshop will touch the past, the state of the art, and future of PCPs. Topics will include: hardness of approximation, PCPs in cryptography and blockchains, no-signaling PCPs, PCPs in P, and Boolean function analysis.
Boaz Barak, Shafi Goldwasser, Eli Ben Sasson, Gil Kalai, Yael Kalai, Guy Kindler, Elchanan Mossel, Christos Papadimitriou, Aviad Rubinstein, Ran Raz, Ronitt Rubinfeld, Oded Schwartz, Irit Dinur, Andrew Yao, and Avi Wigderson.
Nir Bitansky, Esty Kelman, Subhash Khot, Dor Minzer, and Muli Safra