Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Distributed PCP Theorems for Hardness of Approximation in P
event speaker icon
Aviad Rubenstein (Stanford University)
event date icon
Wednesday, 02.05.2018, 12:30
event location icon
Taub 201

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.

Theory Seminar: Distributed PCP Theorems for Hardness of Approximation in P