Pasin Manurangsi, Google

Abstract

While the area of fine-grained and parameterized complexity has provided a framework for proving computational hardness of many fundamental problems, approximation algorithms in this regime have not been well understood until recent years, principally due to a lack of unified tool for proving hardness of approximation. Distributed PCPs--proposed by Abboud, Rubinstein and Williams (FOCS'17)--is a framework that overcomes such a limitation. This approach allows one to translate certain communication protocols to hardness of approximation results in the fine-grained and parameterized regime. It has been successfully employed to proved hardness of approximation for well-studied problems such as nearest neighbor search (Rubinstein, STOC'18) and k-dominating set (Karthik, Laekhanukit and Manurangsi, STOC'18). This talk will give an overview of this framework, with specific focus on these two results.