scientific article; zbMATH DE number 7053341

zbMath1422.68263arXiv1109.6178MaRDI QIDQ5743464

Shai Vardi, Ronitt Rubinfeld, Ning Xie, Noga Alon

Publication date: 10 May 2019

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

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

Related Items (13)

New techniques and tighter bounds for local computation algorithms ⋮ Average Sensitivity of Graph Algorithms ⋮ Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs ⋮ 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 ⋮ Local algorithms for sparse spanning graphs ⋮ When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distributed approximation of capacitated dominating sets
• Property-preserving data reconstruction
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• Derandomized constructions of \(k\)-wise (almost) independent permutations
• On the efficiency of local decoding procedures for error-correcting codes
• The price of being near-sighted
• Distance Approximation in Bounded-Degree and General Sparse Graphs
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• An algorithmic approach to the Lovász local lemma. I
• A parallel algorithmic version of the local lemma
• What Can be Computed Locally?
• An improved constant-time approximation algorithm for maximum~matchings
• On the complexity of distributed graph coloring
• Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time
• Local Monotonicity Reconstruction
• Distributed Computing
• Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy
• Analytic Inequalities
• The Multiplicative Process
• Locally Decodable Codes

This page was built for publication: