5 citations · 8 across the 8 of their papers we have counts for
4 papers · 1 filter
The Hardness of Optimization Problems on the Weighted Massively Parallel Computation Model
Hengzhao Ma, Jianzhong Li
The topology-aware Massively Parallel Computation (MPC) model is proposed and studied recently, which enhances the classical MPC model by the awareness of network topology. The wor…
Turing Machines with Two-level Memory: A Deep Look into the Input/Output Complexity
Hengzhao Ma, Jianzhong Li, Xiangyu Gao +1
The input/output complexity, which is the complexity of data exchange between the main memory and the external memory, has been elaborately studied by a lot of former researchers.…
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…