ARC Colloquium: Aviad Rubinstein (UC Berkeley)

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


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:

Click here to subscribe to the seminar email list:


Event Details


  • Monday, November 6, 2017
    11:00 am - 12:00 pm
Location: Klaus 1116 East