A Workshop on Local Algorithms took place at MSR and MIT, in October 2016. Following are my comments on few of the lectures.

The result is that this can be done with $s(\eps)=O(\eps^{-2})$ and $Q(\eps)$ being quasi-polynomial in $1/\eps$. Indeed, doing it with $Q(\eps)=\poly(1/\eps)$ is open.

Starting with the trivial $n$-way partition, the algorithm proceeds in $O(\log(1/\eps))$ iterations such that in each iteration (if the graph is $H$-minor free then) with constant probability the number of edges (between different parts) is cut by a constant (unless it is already smaller than $\eps n$). In any case, the other invariant are maintained (i.e., each part is a connected component of size at most $s(\eps)$). In the $i$th iteration a new partition oracle is constructed, using oracle access to the original partition and to the partition oracle constructed in the $i-1$st iteration.

Each iteration consists of two steps.

1. Combing parts to reduce number of edges between parts,
which approximately squaring the size of parts.
With constant probability, the number of edges shrinks by a constant.

2. Using a refinement procedure that regains parts of size $s(\eps)$,
but increases the number of edges by an additive $\eps n/2$.

The complexity of each of the two steps is polynomial in the size of the parts on which it operates. So, if you do only (1), which is what was done in prior work, then size of parts after $i$ iterations is of the magnitude $exp(2^i)$ and you end up with parts of size $exp(2^{O(\log(1/\eps))})=\exp(1/\eps)$ and with similar local-computation time. But, by doing (2), you keep parts at size $s(\eps)=\poly(1/\eps)$, and so the cost of implementing the $i$th oracle is only $s(\eps)^{O(i)}$, giving the claimed result

The case in which $\cal H$ contains a single graph was considered in prior works and an almost full characterization of the cases in which the complexity is polynomial in the proximity parameter is known. Turning to the case that $\cal H$ is finite, this current work presents conditions for having such complexity. The sufficient condition is that $\cal H$ contains a bipartite graph, a co-bipartite graph, and a "split" graph. The necessary condition is that $\cal H$ contains a bipartite graph and a co-bipartite graph. (Note that the 2-path is both bipartite and co-bipartite.) Results for the case that $\cal H$ is infinite are also presented, while recalling that each hereditary graph property can be characterized by induced $\cal H$-freeness for some (possibly) infinite $\cal H$.

At one extreme, one interprets locality as constant query complexity, and aims at obtaining the best possible rate (equiv., lowest length overhead). In the case of local testing, one can obtain almost linear length (equiv., polylogarithmic length overhead), and it is not clear if constant rate can be achieved. In the case of local decoding, one can obtain sub-exponential length, and it is not clear if polynomial length can be achieved. (I'd also mention that a notion of relaxed local decoding (see Section 4.2 in BGHSV) can be obtained for length $n=k^c$ for any constant $c>1$, and it is not clear if shorter length can be achieved.)

At the other extreme, one requires codes of constant rate, and aims to minimize the query complexity (i.e., locality). In the case of testing, quasi-poly-logarithmic query complexity can be obtained, and it begs to ask for poly-logarithmic query complexity. In the case of decoding, query complexity $k^{o(1)}$ can be obtained; the current bound is $\exp(\sqrt(\log k))$.

The current work considers the case that the network is a grid (of any constant dimension). In this case, the round complexity of each LCL is either a constant or log-star or equal the diameter of the network, and distinguishing the latter two cases can not be automated (i.e., the problem is undecidable). Nevertheless, it is shown that is the complexity is at most log-star, then an algorithm can be found by a generic reduction to finding an adequate constant-round algorithm. Specifically, the desired algorithm can be decomposed into first finding an MIS, via the known log-star algorithm, and then solving the specific LCL (in constant number of rounds) when given the MIS. An algorithm for solving the latter problem can be found by scanning all possibilities.

See workshop's webpage.

Back to list of Oded's choices.