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)- Local edge colouring of Yao-like subgraphs of unit disk graphs
- A silent self-stabilizing algorithm for the generalized minimal k-dominating set problem
- What can be verified locally?
- Linear-in- lower bounds in the LOCAL model
- Computing large independent sets in a single round
- Constant-time local computation algorithms
- On mobile agent verifiable problems
- Characterizations of classes of graphs recognizable by local computations
- 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
- 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
- Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022
- Survey of local algorithms
- Locally checkable proofs
- Constructing near spanning trees with few local inspections
- Locality and checkability in wait-free computing
- On the locality of some NP-complete problems
- Local computation: lower and upper bounds
- Locally checkable proofs in distributed computing
- Constant space and non-constant time in distributed 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
- Local Terminations and Distributed Computability in Anonymous Networks
- Local Maps: New Insights into Mobile Agent Algorithms
- Leveraging Linial’s Locality Limit
- A Limit to the Power of Multiple Nucleation in Self-assembly
- scientific article; zbMATH DE number 3902710 (Why is no real title available?)
- Checking Global Graph Properties by Means of Local Computations: the Majority Problem
- Local Labeling and Resource Allocation Using Preprocessing
- Local-on-average distributed tasks
- An exponential separation between randomized and deterministic complexity in the LOCAL model
- What can be verified locally?
- A time hierarchy theorem for the LOCAL model
- scientific article; zbMATH DE number 1923048 (Why is no real title available?)
- Survey of distributed decision
- Infinite networks, halting and local algorithms
- On the probe complexity of local computation algorithms
- \((\Delta+1)\) coloring in the congested clique model
- Introduction to local certification
- Locally computable enumerations
- Almost global problems in the LOCAL model
- scientific article; zbMATH DE number 7561278 (Why is no real title available?)
- Derandomizing distributed algorithms with small messages: spanners and dominating set
- Equilibria of Games in Networks for Local Tasks
- The Synergy of Finite State Machines
- Network Decomposition and Distributed Derandomization (Invited Paper)
- Hundreds of impossibility results for distributed computing
- The Distributed Complexity of Locally Checkable Problems on Paths is Decidable
- Computability in anonymous networks: revocable vs. irrecovable outputs
- What can be decided locally without identifiers?
- Veracity radius, capturing the locality of distributed computations
- The impact of locality in the broadcast congested clique model
- LCL problems on grids
- What Can be Sampled Locally?
- Towards a complexity theory for local distributed computing
- Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
- Experimental and Efficient Algorithms
- Space-efficient local computation algorithms
- Logical locality entails frugal distributed computation over graphs (extended abstract)
- Distributed Lower Bounds for Ruling Sets
- Making local algorithms wait-free: the case of ring coloring
- Weak models of distributed computing, with connections to modal logic
- Making local algorithms wait-free: the case of ring coloring
- Representing graphs implicitly using almost optimal space
- scientific article; zbMATH DE number 7765409 (Why is no real title available?)
- Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics
- Distributed algorithms, the Lovász local lemma, and descriptive combinatorics
- Component stability in low-space massively parallel computation
- Distributed approximation of capacitated dominating sets
- Distributed half-integral matching and beyond
- Analysing local algorithms in location-aware quasi-unit-disk graphs
- Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
- Classification of distributed binary labeling problems
- The complexity landscape of distributed locally checkable problems on trees
- Brief announcement: Efficient load-balancing through distributed token dropping
- Brief announcement: Distributed graph problems through an automata-theoretic lens
- An optimal bit complexity randomized distributed MIS algorithm
- Distributed algorithms for covering, packing and maximum weighted matching
- The topology of local computing in networks
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)
