arXiv Open Access 2024

A Note on Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds of the Congested Clique

Andrzej Lingas

Lihat Sumber

Abstrak

We study the possibility of designing $N^{o(1)}$-round protocols for problems of substantially super-linear polynomial-time (sequential) complexity on the congested clique with about $N^{1/2}$ nodes, where $N$ is the input size. We show that the average time complexity of the local computation performed at a clique node (in terms of the size of the data received by the node) in such protocols has to be substantially larger than the time complexity of the given problem.

Topik & Kata Kunci

cs.DC

Penulis (1)

Andrzej Lingas

Format Sitasi

APA MLA BibTeX

Lingas, A. (2024). A Note on Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds of the Congested Clique. https://arxiv.org/abs/2405.15270

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2024
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓