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.
--------------------------------------
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
