A few talks in WOLA'16

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

A SHORT (AND PARTIAL) SURVEY ON PARTITION ORACLES (by Dana Ron)

One version of the problem is as follows. For some fixed graph $H$ (e.g., $K_5$), given oracle access to a bounded-degree $n$-vertex graph $G$ and an error parameter $\eps$, we want to "locally construct" a partition of the vertices of $G$ into connected components such that each has size at most $s(\eps)$ and if $G$ is $H$-minor free then whp there are at most $\eps n$ edges between these parts. By local construction, we mean that each query to the partition oracle should be answered by making at most $Q(\eps)$ queries to the graph. Indeed, the complexity measures are $s$ and $Q$

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

TESTING GRAPH PROPERTIES WITH A POLYNOMIAL QUERY COMPLEXITY (by Asaf Shapira)

For a fixed family of graphs $\cal H$, we consider the set of induced $\cal H$-free graphs and the (query) complexity of testing these sets.

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$.

A LOCAL ALGORITHM FOR CONSTRUCTING SPANNERS IN MINOR-FREE GRAPHS (by Reut Levi)

The task is to implement an oracle that describes a sparse spanning subgraph of the input graph, where sparseness is governed by an approximation parameter $\eps$ such that the $n$-vertex subgraph is required to have at most $(1+\eps) n$ edges. While, in general, answering such queries may require $\Omega({\sqrt n})$ probes to the (bounded-degree) input graph, probe complexity that only depends on $\eps$ (and other fixed parameters) is achievable when the (bounded-degree) graph is minor free. In the current work, this complexity is polynomial in $d/\eps$ and $|H|$, where $d$ is the degree bound and the graph is $H$-minor-free.

ON LIMITS OF LOCAL ALGORITHMS FOR SOLVING RANDOM CONSTRAINT SATISFACTION PROBLEMS (by David Gamarnik)

This work shows that "local" algorithms fail to meet the performance of very simple algorithms for finding large cliques in random graphs (and related CSP problems). In these local algorithms, the membership of a vertex in the clique is determined based on random values assigned to it and to its neighbourhood (i.e., vertices at constant distance from it).

LOCALITY IN CODING THEORY (by Madhu Sudan)

This telegraphic survey focused on two computational problems (i.e., testing and decoding) and two extreme setting of parameters (i.e., the locality parameter and the rate of the code, where in all cases one aims at codes with constant relative distance).

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))$.

DESIGNING LOCAL ALGORITHMS WITH ALGORITHMS (by Jukka Suomela)

The setting is of locally checkable labelling (LCL), where one seeks a distributed algorithm of low round complexity (in the message passing model) for assigning labels to vertices in a way that satisfies some fixed local constraint (on constant size neighborhoods). (E.g., in $k$-colorability the local constraints mandate that each vertex obtains a label in $[k]$ that differs from the labels of its neighbors.)

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.

SUBLINEAR RANDOM-ACCESS GENERATORS FOR PREFERENTIAL ATTACHEMENT GRAPHS (by Adi Rosen)

The aim is to design "local samplers", which are sampling algorithms that support query access to a huge graph that is drawn according to some predetermined distribution. The point is that these algorithms do not sample such a graph upfront but rather sample it on-the-fly in response to queries. These samplers are allowed to maintain a state that is proportional to the number of queries made, and they answer each query in time that is polylogarithmic in the size of the graph. This work provides such a sampler for the distribution of so called "preferential attachement graphs" which is defined by a sequential process in which each new vertex is connected to a random vertex in the current graph. (When directing these edges from the new vertices to the old one, this definition easily supports queries for out-going edges, but not so in the opposite direction.)

The original abstracts and the rest of the program

See workshop's webpage.

Back to list of Oded's choices.