Pasin Manurangsi - Tutorial on Distributed PCPs

Pasin Manurangsi, Google, presents the "Tutorial on Distributed PCPs" at the DIMACS Workshop on Hardness of approximation in P held at Rutgers University on July 21-23, 2025. 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. Workshop webpage: http://dimacs.rutgers.edu/events/details?eID=3156