We present a new model of probabilistically checkable proof (PCP), which we
call "Distributed PCP":
A satisfying assignment (x in {0,1}^n) to a SAT instance is shared between two
parties (Alice knows x_1, ... x_{n/2}, and Bob knows x_{n/2+1},...,x_n).
Their goal is to jointly write a PCP for x, while exchanging little or no
information.
Using our new framework, we obtain, for the first time, PCP-like hardness of
approximation results for problems in P.
Based on joint works with Amir Abboud, Lijie Chen, Shafi Goldwasser, Kaifeng Lyu,
Guy Rothblum, and Ryan Williams.
