Cover Image

On Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds in the MPC Model

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Lingas, Andrzej
Format:	Preprint
Published:	2026
Subjects:	Distributed, Parallel, and Cluster Computing Computational Complexity Data Structures and Algorithms F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Note on Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds of the Congested Clique
by: Lingas, Andrzej
Published: (2024)

Boolean Matrix Multiplication for Highly Clustered Data on the Congested Clique
by: Lingas, Andrzej
Published: (2024)

Approximate all-pairs Hamming distances and 0-1 matrix multiplication
by: Kowaluk, Miroslaw, et al.
Published: (2025)

On the Node-Averaged Complexity of Locally Checkable Problems on Trees
by: Balliu, Alkida, et al.
Published: (2023)

Faster CONGEST Approximation Algorithms for Maximum Weighted Independent Set in Sparse Graphs
by: Faour, Salwa, et al.
Published: (2025)

Decentralized Distributed Graph Coloring: Cluster Graphs
by: Flin, Maxime, et al.
Published: (2024)

Deterministic Fault-Tolerant Local Load Balancing and its Applications against Adaptive Adversaries
by: Kowalski, Dariusz R., et al.
Published: (2025)

High-Quality Multi-Constraint Hypergraph Partitioning via Greedy Rebalancing
by: Maas, Nikolai
Published: (2026)

Low-Depth Spatial Tree Algorithms
by: Baumann, Yves, et al.
Published: (2024)

RadiK: Scalable and Optimized GPU-Parallel Radix Top-K Selection
by: Li, Yifei, et al.
Published: (2025)

The Voronoi Diagram of Weakly Smooth Planar Point Sets in $O(\log n)$ Deterministic Rounds on the Congested Clique
by: Jansson, Jesper, et al.
Published: (2024)

Restless reachability problems in temporal graphs
by: Thejaswi, Suhas, et al.
Published: (2020)

Fast approximate $\ell$-center clustering in high dimensional spaces
by: Kowaluk, Mirosław, et al.
Published: (2025)

Multiplication of 0-1 matrices via clustering
by: Jansson, Jesper, et al.
Published: (2025)

Fast Gossip-based Rumor Spreading using Small Messages
by: Dufoulon, Fabien, et al.
Published: (2026)

Why Canonical Rounds Fail for Optimal Byzantine Resilience
by: Attiya, Hagit, et al.
Published: (2025)

An Algorithm for a Variation of the Shortest Common Superstring Problem
by: Gilfanov, Arthur
Published: (2024)

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
by: Krithika, R., et al.
Published: (2023)

Generalizing Brooks' theorem via Partial Coloring is Hard Classically and Locally
by: Bok, Jan, et al.
Published: (2025)

A Tight Meta-theorem for LOCAL Certification of MSO$_2$ Properties within Bounded Treewidth Graphs
by: Cook, Linda, et al.
Published: (2025)

Graph Threading with Turn Costs
by: Demaine, Erik D., et al.
Published: (2024)

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
by: Dvořák, Pavel, et al.
Published: (2017)

Realizing temporal graphs from fastest travel times
by: Klobas, Nina, et al.
Published: (2023)

A Piecewise Approach for the Analysis of Exact Algorithms
by: Clinch, Katie, et al.
Published: (2024)

Identity Testing for Circuits with Exponentiation Gates
by: Li, Jiatu, et al.
Published: (2025)

Spanning Trees Minimizing Branching Costs
by: Gargano, Luisa, et al.
Published: (2024)

Towards universally optimal sorting algorithms
by: Sen, Sandeep
Published: (2025)

SARRIGUREN: a polynomial-time complete algorithm for random $k$-SAT with relatively dense clauses
by: Sarriguren, Alfredo Goñi
Published: (2024)

NP-Completeness of the Combinatorial Distance Matrix Realisation Problem
by: Fairbairn, David L., et al.
Published: (2024)

Certificate-Sensitive Subset Sum: Realizing Instance Complexity
by: Salas, Jesus
Published: (2025)

When Votes Change and Committees Should (Not)
by: Bredereck, Robert, et al.
Published: (2020)

The World's Fastest Matching Engine Algorithm
by: Yoon, Jake
Published: (2026)

Clock Synchronization Is Almost Impossible with Bounded Memory
by: Charron-Bost, Bernadette, et al.
Published: (2024)

A Decomposition Approach to the Weighted $k$-server Problem
by: Ayyadevara, Nikhil, et al.
Published: (2024)

Sublinear-Time Sampling of Spanning Trees in the Congested Clique
by: Pemmaraju, Sriram V., et al.
Published: (2024)

Obfuscated Consensus
by: Aspnes, James, et al.
Published: (2025)

Improving Efficiency in Near-State and State-Optimal Self-Stabilising Leader Election Population Protocols
by: Gąsieniec, Leszek, et al.
Published: (2025)

Anonymous Self-Stabilising Localisation via Spatial Population Protocols
by: Gąsieniec, Leszek, et al.
Published: (2024)

An Analysis of Avalanche Consensus
by: Amores-Sesar, Ignacio, et al.
Published: (2024)

The consensus number of a shift register equals its width
by: Aspnes, James
Published: (2025)