Algorithms & Randomness Center (ARC)

Aviad Rubinstein (UC Berkeley)

Monday, November 6, 2017

Klaus 1116 East - 11:00 am

Title: Distributed PCP Theorems for Hardness of Approximation in P

Abstract: 

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 CNF formula 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 reductions from the Strong Exponential Time Hypothesis (SETH) to approximation problems in P.

Based in part on joint work with Amir Abboud and Ryan Williams.

--------------------------------------

Speaker's Webpage

Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836

Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu