BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Hengzhao Ma

Hengzhao Ma contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational ComplexityComputation and LanguageComputational GeometryDistributed, Parallel, and Cluster Computing

Trust snapshot

Quick read

Trust 19 - UnverifiedVerification L1Unclaimed author
5works
0followers
4topics
3close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

5 published item(s)

preprint2024arXiv

The PCP-like Theorem for Sub-linear Time Inapproximability

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 inapproximability. Here we try to go further in this direction. Staring from SETH, we first find a problem denoted as Ext-$k$-SAT, which can not be computed in linear time, then devise an efficient MA-like protocol for this problem. To use this protocol to prove the sub-linear time inapproximability of other problems, we devise a new kind of reduction denoted as Ext-reduction, and it is different from existing reduction techniques. We also define two new hardness class, the problems in which can be computed in linear-time, but can not be efficiently approximated in sub-linear time. Some problems are shown to be in the newly defined hardness class.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

A New Model for Massively Parallel Computation Considering both Communication and IO Cost

In the research area of parallel computation, the communication cost has been extensively studied, while the IO cost has been neglected. For big data computation, the assumption that the data fits in main memory no longer holds, and external memory must be used. Therefore, it is necessary to bring the IO cost into the parallel computation model. In this paper, we propose the first parallel computation model which takes IO cost as well as non-uniform communication cost into consideration. Based on the new model, we raise several new problems which aim to minimize the IO and communication cost on the new model. We prove the hardness of these new problems, then design and analyze the approximate algorithms for solving them.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

PCP Theorems, SETH and More: Towards Proving Sub-linear Time Inapproximability

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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Turing Machines with Two-level Memory: A Deep Look into the Input/Output Complexity

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. However, the existing works failed to consider the input/output complexity in a computation model point of view. In this paper we remedy this by proposing three variants of Turing machine that include external memory and the mechanism of exchanging data between main memory and external memory. Based on these new models, the input/output complexity is deeply studied. We discussed the relationship between input/output complexity and the other complexity measures such as time complexity and parameterized complexity, which is not considered by former researchers. We also define the external access trace complexity, which reflects the physical behavior of magnetic disks and gives a theoretical evidence of IO-efficient algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Sub-linear Time Algorithm for Approximating k-Nearest-Neighbor with Full Quality Guarantee

In this paper we propose an algorithm for the approximate k-Nearest-Neighbors problem. According to the existing researches, there are two kinds of approximation criterion. One is the distance criteria, and the other is the recall criteria. All former algorithms suffer the problem that there are no theoretical guarantees for the two approximation criterion. The algorithm proposed in this paper unifies the two kinds of approximation criterion, and has full theoretical guarantees. Furthermore, the query time of the algorithm is sub-linear. As far as we know, it is the first algorithm that achieves both sub-linear query time and full theoretical approximation guarantee.

0 citations0 reviewsNo code linkedOpen access