What Can be Computed Locally?

DOI10.1137/S0097539793254571zbMATH Open0845.68006OpenAlexW2017345786WikidataQ56041881 ScholiaQ56041881MaRDI QIDQ4862796FDOQ4862796

Authors: 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

Recommendations

• What cannot be computed locally!
• Local computation: lower and upper bounds
• What can be verified locally?
• What can be verified locally?
• Generic local computation
• What can be sampled locally?
• What Can be Sampled Locally?
• What can be computed in a distributed system?
• What can be decided locally without identifiers?

zbMATH Keywords

locally checkable labeling

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15) Network design and communication in computer systems (68M10)

Cited In (only showing first 100 items - show all)

• Deciding and verifying network properties locally with few output bits
• On the probe complexity of local computation algorithms
• An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
• Local certification of graphs with bounded genus
• An iterative domain decomposition, spectral finite element method on non-conforming meshes suitable for high frequency Helmholtz problems
• Planarity can be verified by an approximate proof labeling scheme in constant-time
• A hierarchy of local decision
• Local computation: lower and upper bounds
• Weak models of distributed computing, with connections to modal logic
• Allowing each node to communicate only once in a distributed system: shared whiteboard models
• Distributed verification of minimum spanning trees
• Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
• Derandomizing local distributed algorithms under bandwidth restrictions
• Experimental and Efficient Algorithms
• Hundreds of impossibility results for distributed computing
• What can be verified locally?
• Survey of distributed decision
• A silent self-stabilizing algorithm for the generalized minimal \(k\)-dominating set problem
• On mobile agent verifiable problems
• Space-efficient local computation algorithms
• A simple local 3-approximation algorithm for vertex cover
• On the locality of some NP-complete problems
• Locally checkable proofs in distributed computing
• Exact bounds for distributed graph colouring
• Characterizations of classes of graphs recognizable by local computations
• Ramanujan graphings and correlation decay in local algorithms
• Locally checkable proofs
• Title not available (Why is that?)
• Computability in anonymous networks: revocable vs. irrecovable outputs
• Classification of distributed binary labeling problems
• Leveraging Linial’s Locality Limit
• New techniques and tighter bounds for local computation algorithms
• Locality and checkability in wait-free computing
• Locality and checkability in wait-free computing
• A local approximation algorithm for minimum dominating set problem in anonymous planar networks
• Representing graphs implicitly using almost optimal space
• Almost stable matchings by truncating the Gale-Shapley algorithm
• Deterministic local algorithms, unique identifiers, and fractional graph colouring
• Synchronous counting and computational algorithm design
• Towards a complexity theory for local distributed computing
• The impact of locality in the broadcast congested clique model
• What can be verified locally?
• Distributed graph problems through an automata-theoretic Lens
• Local Terminations and Distributed Computability in Anonymous Networks
• Title not available (Why is that?)
• A Limit to the Power of Multiple Nucleation in Self-assembly
• \((\Delta+1)\) coloring in the congested clique model
• An optimal bit complexity randomized distributed MIS algorithm
• Constant-time local computation algorithms
• Title not available (Why is that?)
• Analysing local algorithms in location-aware quasi-unit-disk graphs
• Distributed Lower Bounds for Ruling Sets
• Linear-in-\(\varDelta \) lower bounds in the LOCAL model
• Local approximability of max-min and min-max linear programs
• Veracity radius, capturing the locality of distributed computations
• Distributed graph problems through an automata-theoretic lens
• Distributed approximation of capacitated dominating sets
• Local edge colouring of Yao-like subgraphs of unit disk graphs
• A time hierarchy theorem for the LOCAL model
• Survey of local algorithms
• Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
• Computing large independent sets in a single round
• Distributed algorithms for covering, packing and maximum weighted matching
• LCL problems on grids
• An exponential separation between randomized and deterministic complexity in the LOCAL model
• Network Decomposition and Distributed Derandomization (Invited Paper)
• Almost global problems in the LOCAL model
• Further optimizations of CSIDH: a systematic approach to efficient strategies, permutations, and bound vectors
• What can be decided locally without identifiers?
• Distributed interactive proofs for the recognition of some geometric intersection graph classes
• Local mending
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• The Synergy of Finite State Machines
• Introduction to local certification
• The complexity landscape of distributed locally checkable problems on trees
• Locally computable enumerations
• Title not available (Why is that?)
• Making local algorithms wait-free: the case of ring coloring
• Making local algorithms wait-free: the case of ring coloring
• Fooling views: a new lower bound technique for distributed computations under congestion
• Logical locality entails frugal distributed computation over graphs (extended abstract)
• Constant space and non-constant time in distributed computing
• What Can be Sampled Locally?
• Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics
• Derandomizing distributed algorithms with small messages: spanners and dominating set
• Distributed algorithms, the Lovász local lemma, and descriptive combinatorics
• No sublogarithmic-time approximation scheme for bipartite vertex cover
• Distributed half-integral matching and beyond
• Local Maps: New Insights into Mobile Agent Algorithms
• Almost global problems in the LOCAL model
• The topology of local computing in networks
• Infinite networks, halting and local algorithms
• Can we locally compute sparse connected subgraphs?
• Local-on-average distributed tasks
• Distributed computing in the asynchronous LOCAL model
• What can be sampled locally?
• Local algorithms for sparse spanning graphs
• Brief announcement: Efficient load-balancing through distributed token dropping
• Brief announcement: Distributed graph problems through an automata-theoretic lens
• Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022

This page was built for publication: What Can be Computed Locally?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4862796)