אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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.