Advances in Graph Coloring and Distributed Computing

The field of graph coloring and distributed computing is witnessing significant advancements, with a focus on developing efficient algorithms for solving complex problems. Recent research has led to the development of novel deterministic and randomized algorithms for graph coloring, which have improved upon existing bounds and achieved optimal results in certain cases. Additionally, there have been breakthroughs in distributed computing, including the development of quantum-based solutions for locally checkable labeling problems and parallel algorithms for vertex connectivity. These advancements have the potential to impact various areas of computer science, including blockchain systems, network optimization, and machine learning. Noteworthy papers include: Towards Optimal Distributed Delta Coloring, which presents a O(log n)-round deterministic algorithm for dense constant-degree graphs, and Distributed Quantum Advantage in Locally Checkable Labeling Problems, which demonstrates the first known example of a locally checkable labeling problem that admits asymptotic distributed quantum advantage. Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth is also noteworthy, as it presents a randomized parallel algorithm for k-vertex connectivity with near-linear work and polylogarithmic depth.

Sources

Towards Optimal Distributed Delta Coloring

Monte Carlo Graph Coloring

Commit-Reveal$^2$: Randomized Reveal Order Mitigates Last-Revealer Attacks in Commit-Reveal

Computational Obfuscations and Random Oracles for Derandomizing Asynchronous Consensus

A Customized SAT-based Solver for Graph Coloring

Finding large $k$-colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs

Hollow Victory: How Malicious Proposers Exploit Validator Incentives in Optimistic Rollup Dispute Games

Distributed Quantum Advantage in Locally Checkable Labeling Problems

Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth

Built with on top of