דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Theory Seminar: Distributed PCP Theorems for Hardness of Approximation in P
event speaker icon
אביעד רובינשטיין (אונ' סטנפורד)
event date icon
יום רביעי, 2.5.2018, 12:30
event location icon
טאוב 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.

[בחזרה לאינדקס האירועים]