Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LOCAL ALGORITHMS:
Reports tagged with Local Algorithms:
TR13-055 | 5th April 2013

#### Limits of local algorithms over sparse random graphs

Local algorithms on graphs are algorithms that run in parallel on the nodes of a graph to compute some global structural feature of the graph. Such algorithms use only local information available at nodes to determine local aspects of the global structure, while also potentially using some randomness. Recent research ... more >>>

TR15-019 | 3rd February 2015
Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira

#### Constructing Near Spanning Trees with Few Local Inspections

Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let $G$ be a connected bounded-degree graph. Given an edge $e$ in $G$ we would like ... more >>>

TR20-154 | 10th October 2020
Marcel Dall'Agnol, Tom Gur, Oded Lachish

We prove a general structural theorem for a wide family of local algorithms, which includes property testers, local decoders, and PCPs of proximity. Namely, we show that the structure of every algorithm that makes $q$ adaptive queries and satisfies a natural robustness condition admits a sample-based algorithm with $n^{1- 1/O(q^2 ... more >>> TR21-034 | 9th March 2021 Oded Goldreich #### Robust Self-Ordering versus Local Self-Ordering We study two notions that refers to asymmetric graphs, which we view as graphs having a unique ordering that can be reconstructed by looking at an unlabeled version of the graph. A {\em local self-ordering} procedure for a graph$G\$ is given oracle access to an arbitrary isomorphic copy of ... more >>>

ISSN 1433-8092 | Imprint