The 3rd Workshop on Local Algorithms (WOLA) took place on July 20-22, 2019, in ETH Zurich. While the list of organizers contains six names, the bulk of the work was performed by Mohsen Ghaffari, who should be credited for the success of this workshop, and to Ronitt Rubinfeld who initiated the WOLA series. I found the WOLA'19 program extremely interesting and have learned a lot from attending most of the presentations. In fact, I felt quite exhausted after each of the days. The less exhaustive choices and brief comments that appear below are restricted by my own capacity (and not only by my own taste and interests).
The program of the workshop posted at WOLA19 webpage includes slides of almost all presentations. Below you can find my comments on six of the (45-minutes long) spotlight presentations and on ten of the (17-minutes long) regular presentations.
In both works the easy case is when the graph is rapidly mixing, and the difficulty is coping with the general case. The key idea is using a very weak (and in some sense minimal) notion of rapid mixing; that is, rather than requiring convergence in exponential rate, one requires convergence at a polynomial rate that is higher than the convergence rate on minor-closed graphs (like grids). This weak notion of convergence is shown to suffice for dealing with isolated components that are each rapidly mixing, and its benefit is that it allows a stronger result regarding decomposition of general graphs (i.e., the decomposition provides stronger guarantees regarding the `interaction' between the components)
The main technical tool is a palette sparsification theorem that asserts that if each vertex is assign a logarithmic number of random colors (out of the universal palette of [Delta+1]), then a corresponding $(Delta+1)$-coloring still exists, with high probability over the foregoing choices.
The proof of this theorem combines two different strategies, which are adequate in two different extreme cases: The case that all (but one) vertices have degree at most $0.99 Delta$, and the case that the graph consists of isolated $(Delta+1)$-cliques. In the first case, we consider log-many invocations of a sequential greedy algorithm that colors each vertex with the new random color if such a coloring does not conflicts with its colored neighbors, and observe that in each iteration each uncolored vertex gets colored with probability at least 0.01. In the second case, we consider the bipartite graph having the clique's vertices on one side and the assigned colors on the other size, and argue that this graph has a perfect matching. The highly non-trivial part is dealing with the general case, which is done by a complicated decomposition of any graph to a set of almost cliques that are sparsely connected.
The presentation focuses on showing a $tildeOmega(n^2)$ lower bound on the number of rounds needed for computing the exact minVC. The proof is by reduction from the two-party complexity of disjointness. In the reduction each input is encoded as a bipartite graph on $n+n$ vertices, and two (fixed) gadgets are constructed that connect these two bipartite graphs using few edges that have endpoints in the two gadgets. Each party can simulate the execution of a CONGEST algorithm on the part of the graph that it holds, but CONGEST-model communication between vertices that belong to two different gadgets requires communication in the two-party CC model. Hence, the CC-model complexity is upper-bounded by the product of the round complexity of the CONGEST model and the number of inter-gadget edges, which implies a lower bound on the round complexity that loses only the latter factor.
Of course, the answer to the latter question is that the resulting algorithm solves a related problem, not the original one, which is potentially easier (unless the original problem was already simplified as in the case of `sinkless orientation' restricted to graphs that are locally tree-like). So a key concern when designing such a complexity-reduction process is not to trivialize the resulting problem. Indeed, when seeking to prove a lower bound of $r+1$ rounds, we start from an algorithm of round complexity $r$, perform $r$ round-reduction steps, and seek to obtain a zero-round algorithm that solves a non-trivial problem (i.e., a distributed problem that cannot be solved without any communication).
The core of the round-reduction step is considering a new edge-labeling (subject to vertex-constraints) problem in which the labels are supposed to reflect local views of the neighbors in the original given protocol. The new vertex-constraints will enforce consistency between the view (very much as in Dinur's gap amplification...). If we are lucky, then the resulting labeling problem can be further simplified (in a non-trivial manner); such a simplification is important in order to maintain some understanding of the resulting problem, which is importance since we need to prove the non-triviality of the problem obtained after `many' round-reduction.
When proving the $Omega(log^* n)$ lower bound for 3-coloring, the round-reduction step is from $k$-coloring to $2^k$-coloring, and so we can take $log^* o(n)$ steps and still get a non-trivial problem. When proving the $Omega(log n)$ lower bound for sinkless orientations, each pair of round-reduction steps return to the original problem, which is restricted to graphs with log-neighborhoods that looks as trees.
I selected only ten regular presentations from the program, but found also other ones interesting. My selection is confined to the ones for which I feel that I have something to say. (Most of the following presentations are based on joint work of several researchers, but I only mentioned the name of the presenter. Recall that the entire program of the workshop is posted at WOLA19 webpage (see local copy HERE) and this webpage includes slides of almost all presentations.)
Sampling edges in bounded arboricity graphs by Talya Eden
A crucial point here is that the sampling algorithm generate
edges that are distributed almost uniformly in a strong sense.
Specifically, the generated distribution is close to the target
distribution in a point-wise manner (i.e., each item
occurs with probability that is within a constant factor
of the desired probability). Indeed, we are often satisfied
with generating a distribution that is statistically close
to the desired one (i.e., being close in Total Variation Distance).
This is good enough in applications that use a small number
of samples and output a bounded value (e.g., for $A:U\to[0,1]$,
it holds that if $G$ is $\esp$-close to $T$ (in TVD),
then $E[A(G)] = E[A(T)]\pm\eps$). But for applications that produce
unbounded values being statistically close may not suffice,
whereas the stronger notion of point-wise approximation
does suffice; for example, if $Prob[G=e] = (1\pm\eps) Prob[T=e]$,
then $E[A(G)] = (1\pm\eps) E[A(T)]$ for every $A$
(including $A$ such that $Prob[A(G) \gg 1/\eps] = \eps$
and $Prob[A(G)=0] = 1-\eps$).
On Solving Linear Systems in Sublinear Time by Robert Krauthgamer
This work appeared as 5th entry in my report of ITCS19
(see Choice 258).
I wish to highlight (again...) the fact that this work
suggest to consider Local Computation Algorithms
for various algebraic and numerical problems,
whereas so far LCA were considered only for graph theoretic problems.
Property testing of the Boolean rank by Michal Parnas
The Boolean rank is defined for Boolean matrices under Boolean operations
(i.e., addition is replaced by logical OR, whereas multiplication
corresponds to a Boolean AND). It equals the ND communication complexity
of the two-argument function defined by the matrix, and is NP-Hard to compute.
This work presents an $\esp$-tester (one-sided error and non-adaptive)
for having Boolean rank $r$
that operates in time polynomial in $r/\eps$.
(Such a result was known for the standard (i.e., real) rank.)
For binary rank (i.e., rank over GF(2)), they have an $\eps$-tester
of complexity exponential in the rank, and ask whether this
can be improved to polynomial.
Local Access to Huge Random Objects through Partial Sampling
by Amartya Shankha Biswas
I was happy to see an interesting work that refers to
the direction initiated in the work
On the Implementation of Huge Random Objects.
Generating Erdos-Renyi G(n,p) graphs is trivial if one only
needs to support adjacency queries, but here they also want
to support (next and random) neighbor queries.
These additional queries are easy to support when $p$ is
extremely high (e.g., $p=Omega(1)$) and are known to be supported
when $p$ is extremely low (e.g., $p=O(1/n)$),
but here they focus on the intermediate range (e.g., $p=1/sqrt(n)$).
The construction uses small memory that grows with the number of queries,
but I conjecture that one can get a memoriless implementation
as sought by the aforementioned work.
Time hierarchies of distributed complexities by Alkida Balliu
This presentation surveyed the fascinating structure of the round complexity
(in the LOCAL model) of Local Checkable Labeling problems.
The picture in case of paths and cycles is quite simple:
There are only three possible (deterministic) complexities
(i.e., Theta(1), Theta(log^* n), and Theta(log n)).
For general trees and general graphs, the picture is
more complex with infinitely many number of possibilities.
Specifically, for trees, we can also see (deterministic = randomized)
complexities of the form $n^{1/k}$ for any natural $k$ as well as
an exponential gap between deterministic and randomness complexity
(at $log n$ vs $loglog n$).
On the Volume Complexity of LCLs by Will Rosenbaum
Taking a closer look at the LOCAL model, it is suggested
to consider algorithms that explicitly and adaptively
query for a specified neighbor of a visited vertex
(by specifying the port number and obtaining the vertex's ID
as well as its degree and local input if relevant).
That is, at each round, the processor at each vertex
may query the graph about neighbors of vertices revealed to it so far.
The volume complexity of an execution is the number of queries made
by the most active processor in that execution.
This work presents hierarchy results for volume complexity
and compares them to the results surveyed in the previous presentation.
Phase transitions in the independent sets of random graphs
by Endre Csoka
This presentation highlights a possible application of the study
of random graphs. Specifically, if for some parameter random
graphs have a certain value (for that parameter) whereas they
cannot be distinguished within some computation resources from
graphs that have a different value (for the same parameter),
then we get a lower bound on the complexity of computing the parameter.
As an assertion, this is trivial, but the point is that in some cases
it may be useful to use it (and use a known but non-trivial result
about the behavior of random graphs).
Optimal Distributed Covering Algorithms by Guy Even
The presentation focused on a distributed algorithm for finding
an approximate minimum vertex cover in $f$-uniform hypergraphs,
for any fixed $f$ (e.g., $f=2$ corresponds to the standard minVC).
It obtains an approximation factor of $f+\eps$ in
time $poly(\log(n/\eps))$, improving over a prior bound
that was polynomial in $1/\eps$ and $log n$.
Guy highlighted the fact that this improvement allows
to set $\eps=1/2n$ and so obtain a 2-factor approximation of minVC,
but I think that improving the dependence of the complexity on
the approximation parameter is a natural and important issue
when dealing with approximation algorithms.
Guy's model presentation stroke me as a tribute to his father,
Shimon Even,
who was famous for his crystal clear presentations.
Fast Approximate Shortest Paths in the Congested Clique
by Michal Dory
This presentation surveyed a host of new algorithms
for finding approximate shortest paths in the CONGEST model.
In particular, for APSP they obtain a constant-factor
approximation algorithm running in polylogarithmic time.
All results are obtained by clever use of sparse matrix
multiplication, while overcoming the fact that the relevant
matrices don't seem sparse on the face of it.
Breaking Quadratic Time for Small Vertex Connectivity
by Sorrachai Yingchareonthawornchai
This work appeared as 3rd entry in my report of STOC19
(see Choice 269).
As in STOC19, the declared take-home message
was Local algorithms are useful for vertex connectivity.
The current presentation, however, includes some
improvements over the results presented in STOC.
Specifically, the complexity of the exact algorithm
was improved from $tildeO(m + n^{4/3}k^{7/3})$
(which is $tilde(n^{4/3})$ for $m=O(n)$ and $k=O(1)$)
to $tildeO(m + n k^3)$ (which is $tildeO(n)$ for $m=O(n)$ and $k=O(1)$),
where $k$ is the (sought value of the) vertex connectivity.
Furthermore, it presents a one-sided error $\eps$-tester
for $k$-vertex-connectivity of complexity $tildeO(k/\eps^2)$
(improving over a known $tildeO((2/\eps)^{k+1})$ bound).