Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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

Lingas, Andrzej LU (2025) In Parallel Processing Letters 35(03n04).
Abstract

We study the possibility of designing No(1)-round protocols for problems of substantially super-linear polynomial-time (sequential) complexity on the congested clique with about N1/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.

Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Congested clique, number of rounds, time complexity
in
Parallel Processing Letters
volume
35
issue
03n04
article number
2550010
publisher
World Scientific Publishing
external identifiers
  • scopus:105012842493
ISSN
0129-6264
DOI
10.1142/S0129626425500100
language
English
LU publication?
yes
additional info
Publisher Copyright: © 2025 World Scientific Publishing Company.
id
ce009b06-b714-4f6a-8413-8399ed38754c
date added to LUP
2025-12-19 13:06:32
date last changed
2025-12-19 13:07:19
@article{ce009b06-b714-4f6a-8413-8399ed38754c,
  abstract     = {{<p>We study the possibility of designing No(1)-round protocols for problems of substantially super-linear polynomial-time (sequential) complexity on the congested clique with about N1/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.</p>}},
  author       = {{Lingas, Andrzej}},
  issn         = {{0129-6264}},
  keywords     = {{Congested clique; number of rounds; time complexity}},
  language     = {{eng}},
  number       = {{03n04}},
  publisher    = {{World Scientific Publishing}},
  series       = {{Parallel Processing Letters}},
  title        = {{A Note on Solving Problems of Substantially Super-linear Complexity in N o (1) Rounds of the Congested Clique}},
  url          = {{http://dx.doi.org/10.1142/S0129626425500100}},
  doi          = {{10.1142/S0129626425500100}},
  volume       = {{35}},
  year         = {{2025}},
}