New techniques and tighter bounds for local computation algorithms
From MaRDI portal
Publication:2628795
DOI10.1016/j.jcss.2016.05.007zbMath1344.68036arXiv1404.5398OpenAlexW1520166099MaRDI QIDQ2628795
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
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05) Distributed algorithms (68W15)
Related Items (6)
Average Sensitivity of Graph Algorithms ⋮ Unnamed Item ⋮ Constant-time local computation algorithms ⋮ Local computation algorithms for graphs of non-constant degrees ⋮ Unnamed Item ⋮ Best of two local models: centralized local and distributed local algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Local computation algorithms for graphs of non-constant degrees
- Balls into non-uniform bins
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- Universal classes of hash functions
- Constant-Time Local Computation Algorithms
- Converting Online Algorithms to Local Computation Algorithms
- A Local Computation Approximation Scheme to Maximum Matching
- Pseudorandomness
- Survey of local algorithms
- Deterministic Stateless Centralized Local Algorithms for Bounded Degree Graphs
- A Brief Introduction to Property Testing
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Sublinear Time Algorithms
- How asymmetry helps load balancing
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- Locality in Distributed Graph Algorithms
- Balanced Allocations
- An Improved Distributed Algorithm for Maximal Independent Set
- What Can be Computed Locally?
- Fast Pseudorandomness for Independence and Load Balancing
- Local Graph Partitions for Approximation and Testing
- lgorithmic and Analysis Techniques in Property Testing
- Fast Distributed Coloring Algorithms for Triangle-Free Graphs
- COMPRESSED REPRESENTATIONS OF PERMUTATIONS, AND APPLICATIONS
- Theory of Cryptography
This page was built for publication: New techniques and tighter bounds for local computation algorithms