PCP Theorems, SETH and More: Towards Proving Sub-linear Time Inapproximability
This work addresses the problem of guiding research in sub-linear time approximation algorithms for theoretical computer scientists, though it is incremental as it builds on prior distributed PCP frameworks.
The paper tackles proving inapproximability for sub-linear time algorithms by establishing a sub-linear PCP theorem, showing it can derive both existing and new inapproximability results, but fails in the linear case.
In this paper we propose the PCP-like theorem for sub-linear time inapproximability. Abboud et al. have devised the distributed PCP framework for sub-quadratic time inapproximability. We show that the distributed PCP theorem can be generalized for proving arbitrary polynomial time inapproximability, but fails in the linear case. We prove the sub-linear PCP theorem by adapting from an MA-protocol for the Set Containment problem, and show how to use the theorem to prove both existing and new inapproximability results, exhibiting the power of the sub-linear PCP theorem. Considering the emerging research works on sub-linear time algorithms, the sub-linear PCP theorem is important in guiding the research in sub-linear time approximation algorithms.