Space-efficient local computation algorithms

MaRDI QIDQ5743464zbMATH OpenFDO

Authors Noga Alon, Ronitt Rubinfeld, Shai Vardi, Ning Xie

Publication date 10 May 2019

Full work available at URL https://arxiv.org/abs/1109.6178, https://dl.acm.org/citation.cfm?id=2095205

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Nonnumerical algorithms (68W05) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• New techniques and tighter bounds for local computation algorithms
• Converting online algorithms to local computation algorithms
• Constant-time local computation algorithms
• Constant-Time Local Computation Algorithms
• Local computation algorithms for graphs of non-constant degrees

Cites work

• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A parallel algorithmic version of the local lemma
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• An algorithmic approach to the Lovász local lemma. I
• An improved constant-time approximation algorithm for maximum~matchings
• Analytic Inequalities
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• Derandomized constructions of \(k\)-wise (almost) independent permutations
• Distance Approximation in Bounded-Degree and General Sparse Graphs
• Distributed approximation of capacitated dominating sets
• Distributed Computing
• scientific article; zbMATH DE number 5506230 (Why is no real title available?)
• Local monotonicity reconstruction
• Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time
• Locally Decodable Codes
• On the complexity of distributed graph coloring
• On the efficiency of local decoding procedures for error-correcting codes
• Property-preserving data reconstruction
• Space-efficient local computation algorithms
• Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy
• The Multiplicative Process
• The price of being near-sighted
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• What Can be Computed Locally?

Cited in

(26)

• Analysis of local enumeration and storage schemes in HPF
• Constant-time local computation algorithms
• Best of two local models: centralized local and distributed local algorithms
• Local algorithms for sparse spanning graphs
• New techniques and tighter bounds for local computation algorithms
• Constant-Time Local Computation Algorithms
• Converting online algorithms to local computation algorithms
• scientific article; zbMATH DE number 1837654 (Why is no real title available?)
• Local algorithms for bounded degree sparsifiers in sparse graphs
• On the probe complexity of local computation algorithms
• scientific article; zbMATH DE number 7376014 (Why is no real title available?)
• Local computation algorithms for spanners
• When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
• Local computation algorithms for graphs of non-constant degrees
• Space-efficient local computation algorithms
• Average Sensitivity of Graph Algorithms
• Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics
• Local MST computation with short advice
• Spanning adjacency oracles in sublinear time
• Local distributed rounding: generalized to MIS, matching, set cover, and beyond
• Nearly optimal local algorithms for constructing sparse spanners of clusterable graphs
• Locally computing edge orientations
• Agnostic proper learning of monotone functions: beyond the black-box correction barrier
• Local computation algorithms for knapsack: impossibility results, and how to avoid them
• A fast coloring oracle for average case hypergraphs
• A 0.51-approximation of maximum matching in sublinear \(n^{1.5}\) time

This page was built for publication: Space-efficient local computation algorithms

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