Cover Image

Complexity landscape for local certification

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bousquet, Nicolas, Feuilloley, Laurent, Zeitoun, Sébastien
Format:	Preprint
Published:	2025
Subjects:	Distributed, Parallel, and Cluster Computing Discrete Mathematics Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Renaming in distributed certification
by: Bousquet, Nicolas, et al.
Published: (2024)

Local certification of forbidden subgraphs
by: Bousquet, Nicolas, et al.
Published: (2024)

A subquadratic certification scheme for P5-free graphs
by: Bousquet, Nicolas, et al.
Published: (2024)

Global certification via perfect hashing
by: Bousquet, Nicolas, et al.
Published: (2024)

Reductions in local certification
by: Esperet, Louis, et al.
Published: (2025)

Parallelizing the Approximate Minimum Degree Ordering Algorithm: Strategies and Evaluation
by: Chang, Yen-Hsiang, et al.
Published: (2025)

Local Ratio based Real-time Job Offloading and Resource Allocation in Mobile Edge Computing
by: Gao, Chuanchao, et al.
Published: (2025)

Computing in Anonymous Dynamic Networks Is Linear
by: Di Luna, Giuseppe A., et al.
Published: (2022)

Simpler and More General Distributed Coloring Based on Simple List Defective Coloring Algorithms
by: Fuchs, Marc, et al.
Published: (2024)

Efficient Parallel $(Δ+1)$-Edge-Coloring
by: Elkin, Michael, et al.
Published: (2026)

Lower bound for constant-size local certification
by: Martínez, Virgina Ardévol, et al.
Published: (2022)

Scheduled Jacobian Chaining
by: Märtens, Simon, et al.
Published: (2025)

A Randomised Approach to Distributed Sorting
by: Olesker-Taylor, Sam
Published: (2025)

Fast algorithms for Vizing's theorem on bounded degree graphs
by: Bernshteyn, Anton, et al.
Published: (2023)

Model-Agnostic Approximation of Constrained Forest Problems
by: Coupette, Corinna, et al.
Published: (2024)

GenTT: Generate Vectorized Codes for General Tensor Permutation
by: Chen, Yaojian, et al.
Published: (2025)

Optimal local certification on graphs of bounded pathwidth
by: Baterisna, Dan Alden, et al.
Published: (2025)

Distance-based certification for leader election in meshed graphs and local recognition of their subclasses
by: Chalopin, Jérémie, et al.
Published: (2026)

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

Binsparse: A Specification for Cross-Platform Storage of Sparse Matrices and Tensors
by: Brock, Benjamin, et al.
Published: (2025)

Tight Bounds on the Message Complexity of Distributed Tree Verification
by: Kutten, Shay, et al.
Published: (2024)

Overlay Network Construction: Improved Overall and Node-Wise Message Complexity
by: Chang, Yi-Jun, et al.
Published: (2024)

The Online Pause and Resume Problem: Optimal Algorithms and An Application to Carbon-Aware Load Shifting
by: Lechowicz, Adam, et al.
Published: (2023)

Reducing Matroid Optimization to Basis Search
by: Streit, Robert, et al.
Published: (2024)

How local constraints influence network diameter and applications to LCL generalizations
by: Bousquet, Nicolas, et al.
Published: (2024)

Efficient Dynamic MaxFlow Computation on GPUs
by: Kannappan, Shruthi, et al.
Published: (2025)

Towards Optimal Distributed Edge Coloring with Fewer Colors
by: Jakob, Manuel, et al.
Published: (2025)

Perfect Matching with Few Link Activations
by: Mirault, Hugo, et al.
Published: (2025)

Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set
by: Ghaffari, Mohsen, et al.
Published: (2025)

Robust Distributed Arrays: Provably Secure Networking for Data Availability Sampling
by: Feist, Dankrad, et al.
Published: (2025)

Designing Parallel Algorithms for Community Detection using Arachne
by: Li, Fuhuan, et al.
Published: (2025)

New Distributed Interactive Proofs for Planarity: A Matter of Left and Right
by: Gil, Yuval, et al.
Published: (2025)

WarpSpeed: A High-Performance Library for Concurrent GPU Hash Tables
by: McCoy, Hunter, et al.
Published: (2025)

Near-Optimal Distributed Ruling Sets for Trees and High-Girth Graphs
by: Baumecker, Malte, et al.
Published: (2025)

HiPerMotif: Novel Parallel Subgraph Isomorphism in Large-Scale Property Graphs
by: Dindoost, Mohammad, et al.
Published: (2025)

Improved Byzantine Agreement under an Adaptive Adversary
by: Dufoulon, Fabien, et al.
Published: (2025)

A Fast-Converging Decentralized Approach to the Weighted Minimum Vertex Cover Problem
by: Mordacchini, Matteo, et al.
Published: (2025)

Constrained Cuts, Flows, and Lattice-Linearity
by: Streit, Robert, et al.
Published: (2025)

Time-Optimal and Energy-Efficient Deterministic Consensus
by: Meir, Shachar, et al.
Published: (2025)

BLEST: Blazingly Efficient BFS using Tensor Cores
by: Elbek, Deniz, et al.
Published: (2025)