New techniques and tighter bounds for local computation algorithms

DOI10.1016/j.jcss.2016.05.007zbMath1344.68036arXiv1404.5398OpenAlexW1520166099MaRDI QIDQ2628795

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

pseudorandomnesssublinear algorithmslocal computation algorithms

Mathematics Subject Classification ID

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