What Can be Computed Locally?
From MaRDI portal
Publication:4862796
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?
Cited in
(only showing first 100 items - show all)- Network Decomposition and Distributed Derandomization (Invited Paper)
- Distributed interactive proofs for the recognition of some geometric intersection graph classes
- Local mending
- What can be decided locally without identifiers?
- Constructing near spanning trees with few local inspections
- Equilibria of Games in Networks for Local Tasks
- Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
- Deciding and verifying network properties locally with few output bits
- Component stability in low-space massively parallel computation
- The Synergy of Finite State Machines
- Introduction to local certification
- On the probe complexity of local computation algorithms
- 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
- An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
- The complexity landscape of distributed locally checkable problems on trees
- Planarity can be verified by an approximate proof labeling scheme in constant-time
- A hierarchy of local decision
- Locally computable enumerations
- Local computation: lower and upper bounds
- scientific article; zbMATH DE number 7561278 (Why is no real title available?)
- Weak models of distributed computing, with connections to modal logic
- Fooling views: a new lower bound technique for distributed computations under congestion
- Allowing each node to communicate only once in a distributed system: shared whiteboard models
- Making local algorithms wait-free: the case of ring coloring
- Making local algorithms wait-free: the case of ring coloring
- Distributed verification of minimum spanning trees
- Logical locality entails frugal distributed computation over graphs (extended abstract)
- Derandomizing local distributed algorithms under bandwidth restrictions
- Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
- Experimental and Efficient Algorithms
- Constant space and non-constant time in distributed computing
- Hundreds of impossibility results for distributed computing
- A silent self-stabilizing algorithm for the generalized minimal k-dominating set problem
- What can be verified locally?
- Survey of distributed decision
- On mobile agent verifiable problems
- What Can be Sampled Locally?
- A simple local 3-approximation algorithm for vertex cover
- Space-efficient local computation algorithms
- On the locality of some NP-complete problems
- Characterizations of classes of graphs recognizable by local computations
- Locally checkable proofs in distributed computing
- Exact bounds for distributed graph colouring
- Ramanujan graphings and correlation decay in local algorithms
- Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics
- Locally checkable proofs
- scientific article; zbMATH DE number 7765409 (Why is no real title available?)
- Derandomizing distributed algorithms with small messages: spanners and dominating set
- Computability in anonymous networks: revocable vs. irrecovable outputs
- Leveraging Linial’s Locality Limit
- Distributed algorithms, the Lovász local lemma, and descriptive combinatorics
- No sublogarithmic-time approximation scheme for bipartite vertex cover
- Classification of distributed binary labeling problems
- Locality and checkability in wait-free computing
- New techniques and tighter bounds for local computation algorithms
- Locality and checkability in wait-free computing
- A local approximation algorithm for minimum dominating set problem in anonymous planar networks
- Deterministic local algorithms, unique identifiers, and fractional graph colouring
- Synchronous counting and computational algorithm design
- Almost stable matchings by truncating the Gale-Shapley algorithm
- Representing graphs implicitly using almost optimal space
- Distributed half-integral matching and beyond
- Local Maps: New Insights into Mobile Agent Algorithms
- Towards a complexity theory for local distributed computing
- The impact of locality in the broadcast congested clique model
- Almost global problems in the LOCAL model
- What can be verified locally?
- Distributed graph problems through an automata-theoretic Lens
- Local Terminations and Distributed Computability in Anonymous Networks
- scientific article; zbMATH DE number 3902710 (Why is no real title available?)
- A Limit to the Power of Multiple Nucleation in Self-assembly
- An optimal bit complexity randomized distributed MIS algorithm
- The topology of local computing in networks
- Can we locally compute sparse connected subgraphs?
- \((\Delta+1)\) coloring in the congested clique model
- Infinite networks, halting and local algorithms
- Constant-time local computation algorithms
- Analysing local algorithms in location-aware quasi-unit-disk graphs
- Local-on-average distributed tasks
- Local approximability of max-min and min-max linear programs
- Linear-in- lower bounds in the LOCAL model
- scientific article; zbMATH DE number 1923048 (Why is no real title available?)
- Distributed computing in the asynchronous LOCAL model
- Distributed Lower Bounds for Ruling Sets
- 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
- What can be sampled locally?
- Local algorithms for sparse spanning graphs
- Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022
- A time hierarchy theorem for the LOCAL model
- Distributed algorithms for covering, packing and maximum weighted matching
- Survey of local algorithms
- Computing large independent sets in a single round
- Brief announcement: Efficient load-balancing through distributed token dropping
- Brief announcement: Distributed graph problems through an automata-theoretic lens
- Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
- Toward more localized local algorithms: removing assumptions concerning global knowledge
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)
