10 citations · 38 across the 37 of their papers we have counts for
4 papers · 1 filter
Sublinear-time Reductions for Big Data Computing
Xiangyu Gao, Jianzhong Li, Dongjing Miao
With the rapid popularization of big data, the dichotomy between tractable and intractable problems in big data computing has been shifted. Sublinear time, rather than polynomial t…
The PCP-like Theorem for Sub-linear Time Inapproximability
Hengzhao Ma, Jianzhong Li
In this paper we propose the PCP-like theorem for sub-linear time inapproximability. Abboud et al. have devised the distributed PCP framework for proving sub-quadratic time inappro…
PCP Theorems, SETH and More: Towards Proving Sub-linear Time Inapproximability
Hengzhao Ma, Jianzhong Li
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 inapproximabili…
Recognizing the Tractability in Big Data Computing
Xiangyu Gao, Jianzhong Li, Dongjing Miao +1
Due to the limitation on computational power of existing computers, the polynomial time does not works for identifying the tractable problems in big data computing. This paper adop…