New techniques and tighter bounds for local computation algorithms

DOI10.1016/J.JCSS.2016.05.007MaRDI QIDQ2628795zbMATH OpenOpenAlexFDO

Authors Omer Reingold, Shai Vardi

Publication date 15 July 2016

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.5398

zbMATH Keywords

local computation algorithmspseudorandomnesssublinear algorithms

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Distributed algorithms (68W15)

Abstract: Given an input $x$, and a search problem $F$, local computation algorithms (LCAs) implement access to specified locations of $y$ in a legal output $yinF(x)$, using polylogarithmic time and space. Mansour et al., (2012), had previously shown how to convert certain online algorithms to LCAs. In this work, we expand on that line of work and develop new techniques for designing LCAs and bounding their space and time complexity. Our contributions are fourfold: (1) We significantly improve the running times and space requirements of LCAs for previous results, (2) we expand and better define the family of online algorithms which can be converted to LCAs using our techniques, (3) we show that our results apply to a larger family of graphs than that of previous results, and (4) our proofs are simpler and more concise than the previous proof methods. For example, we show how to construct LCAs that require $O(lognloglogn)$ space and $O(lo{g}^{2}n)$ time (and expected time $O(loglogn)$) for problems such as maximal matching on a large family of graphs, as opposed to the henceforth best results that required $O(lo{g}^{3}n)$ space and $O(lo{g}^{4}n)$ time, and applied to a smaller family of graphs.

Recommendations

• Constant-time local computation algorithms
• Constant-Time Local Computation Algorithms
• Space-efficient local computation algorithms
• Local computation algorithms for graphs of non-constant degrees
• Converting online algorithms to local computation algorithms

Cites work

• A Brief Introduction to Property Testing
• A Local Computation Approximation Scheme to Maximum Matching
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Algorithmic and analysis techniques in property testing
• An Improved Distributed Algorithm for Maximal Independent Set
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• Balanced Allocations
• Balls into non-uniform bins
• Compressed representations of permutations, and applications
• Constant-Time Local Computation Algorithms
• Converting online algorithms to local computation algorithms
• Data streams: algorithms and applications.
• Deterministic stateless centralized local algorithms for bounded degree graphs
• Fast distributed coloring algorithms for triangle-free graphs
• Fast pseudorandomness for independence and load balancing (extended abstract)
• How asymmetry helps load balancing
• scientific article; zbMATH DE number 605729 (Why is no real title available?)
• Local computation algorithms for graphs of non-constant degrees
• Local Graph Partitions for Approximation and Testing
• Locality in Distributed Graph Algorithms
• Marriage, honesty, and stability
• Pseudorandomness
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Space-efficient local computation algorithms
• Sublinear time algorithms
• Survey of local algorithms
• Theory of Cryptography
• Universal classes of hash functions
• What Can be Computed Locally?

Cited in

(14)

• Constant-time local computation algorithms
• Best of two local models: centralized local and distributed local algorithms
• Input locality and hardness amplification
• A new approach on locally checkable problems
• Constant-Time Local Computation Algorithms
• Converting online algorithms to local computation algorithms
• On the probe complexity of local computation algorithms
• Local computation algorithms for spanners
• Local computation algorithms for graphs of non-constant degrees
• Space-efficient local computation algorithms
• A Local Criterion for Polynomial-Time Stratified Computations
• Average Sensitivity of Graph Algorithms
• Spanning adjacency oracles in sublinear time
• Agnostic proper learning of monotone functions: beyond the black-box correction barrier

This page was built for publication: New techniques and tighter bounds for local computation algorithms

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