Abstract:We study the possibility of designing $N^{o(1)}$-round protocols for
problems of substantially super-linear polynomial-time (sequential)
complexity in the model of Massively Parallel Computation, where $N$
is the input size. We show that if the machines are not equipped
with relatively large local memory and their number does not exceed
$N$, then the exponent of the average time complexity of the local
computation performed by a machine in a round (in terms of local
memory size) in such protocols must be larger than the exponent of
the time complexity of the given problem.
From: Andrzej Lingas [view email]
[v1]
Tue, 5 May 2026 05:36:15 UTC (14 KB)
[v2]
Tue, 8 Sep 2026 13:40:09 UTC (15 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。