*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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
