In this paper we propose the PCP-like theorem for sub-linear time inapproximability. Abboud et  . 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 borrow similar proof techniques from \mbox{%DIFAUXCMD Abboud2017 the sub-linear time PCP , and show how to use it to prove both existing and new inapproximability results . These results exhibits the power of the sub-linear PCP theorem proposed in this paper . 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.
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.
A
al
R
borrow similar proof techniques from \mbox{%DIFAUXCMD Abboud2017
prove
R
time PCP
PCP theorem by adapting from an MA-protocol for the Set Containment problem
R
it
the theorem
R
. These results exhibits
, exhibiting
D
proposed in this paper