What Can be Computed Locally?
From MaRDI portal
Publication:4862796
DOI10.1137/S0097539793254571zbMath0845.68006WikidataQ56041881 ScholiaQ56041881MaRDI QIDQ4862796
Moni Naor, Larry J. Stockmeyer
Publication date: 15 September 1996
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539793254571
68M10: Network design and communication in computer systems
68R05: Combinatorics in computer science
68R10: Graph theory (including graph drawing) in computer science
68W10: Parallel algorithms in computer science
68W15: Distributed algorithms
Related Items
An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model, A Time Hierarchy Theorem for the LOCAL Model, Unnamed Item, Unnamed Item, Almost global problems in the LOCAL model, Introduction to local certification, Network Decomposition and Distributed Derandomization (Invited Paper), Hundreds of impossibility results for distributed computing, (Delta+1) Coloring in the Congested Clique Model, The Impact of Locality in the Broadcast Congested Clique Model, Equilibria of Games in Networks for Local Tasks, Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set, Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes, Unnamed Item, Representing graphs implicitly using almost optimal space, How long it takes for an ordinary node with an ordinary ID to output?, Weak models of distributed computing, with connections to modal logic, Making local algorithms wait-free: the case of ring coloring, Distributed Lower Bounds for Ruling Sets, Unnamed Item, Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics, Locally checkable problems in rooted trees, Distributed algorithms, the Lovász local lemma, and descriptive combinatorics, Component stability in low-space massively parallel computation, Lower bound for constant-size local certification, Distributed half-integral matching and beyond, Distributed approximation of capacitated dominating sets, Analysing local algorithms in location-aware quasi-unit-disk graphs, An optimal bit complexity randomized distributed MIS algorithm, Distributed algorithms for covering, packing and maximum weighted matching, Local approximability of max-min and min-max linear programs, A local approximation algorithm for minimum dominating set problem in anonymous planar networks, Synchronous counting and computational algorithm design, Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time, Deterministic local algorithms, unique identifiers, and fractional graph colouring, A simple local 3-approximation algorithm for vertex cover, Local edge colouring of Yao-like subgraphs of unit disk graphs, A silent self-stabilizing algorithm for the generalized minimal \(k\)-dominating set problem, Node labels in local decision, What can be verified locally?, Linear-in-\(\varDelta \) lower bounds in the LOCAL model, Computing large independent sets in a single round, Constant-time local computation algorithms, On mobile agent verifiable problems, Distributed verification of minimum spanning trees, Almost stable matchings by truncating the Gale-Shapley algorithm, Almost global problems in the LOCAL model, Deciding and verifying network properties locally with few output bits, Local mending, Distributed interactive proofs for the recognition of some geometric intersection graph classes, Local certification of graphs with bounded genus, Distributed graph problems through an automata-theoretic Lens, Planarity can be verified by an approximate proof labeling scheme in constant-time, An iterative domain decomposition, spectral finite element method on non-conforming meshes suitable for high frequency Helmholtz problems, What can be sampled locally?, Derandomizing local distributed algorithms under bandwidth restrictions, A hierarchy of local decision, Fooling views: a new lower bound technique for distributed computations under congestion, Further optimizations of CSIDH: a systematic approach to efficient strategies, permutations, and bound vectors, Randomized distributed decision, No sublogarithmic-time approximation scheme for bipartite vertex cover, Local algorithms for sparse spanning graphs, Allowing each node to communicate only once in a distributed system: shared whiteboard models, Can we locally compute sparse connected subgraphs?, Locality and checkability in wait-free computing, Toward more localized local algorithms: removing assumptions concerning global knowledge, New techniques and tighter bounds for local computation algorithms, Distributed graph problems through an automata-theoretic lens, Constructing near spanning trees with few local inspections, Unnamed Item, Locality and Checkability in Wait-Free Computing, An Optimal Bit Complexity Randomized Distributed MIS Algorithm (Extended Abstract), Ramanujan graphings and correlation decay in local algorithms, Exact Bounds for Distributed Graph Colouring, Constant space and non-constant time in distributed computing, Local Maps: New Insights into Mobile Agent Algorithms, Leveraging Linial’s Locality Limit, A Limit to the Power of Multiple Nucleation in Self-assembly
