(Piotr Indyk reports from Day 4 at Sublinear Algorithms. Includes contributions from Sariel Har Peled.)

The first session of the day was dedicated to distributed algorithms. It was headlined by Roger Wattenhofer, who gave a very nice overview of the area. Distributed algorithms have recently found applications in sub-linear world, e.g., see the talks on Monday. Distributed algorithms communicate along the edges of a graph, and the algorithm complexity is measured in rounds of communication.

The central character in Roger’s talk was the Maximal Independent Set (MIS) problem. Despite many years of research on this problem, some basic questions are still open (e.g., is there a deterministic algorithm with $\textrm{polylog} n$ rounds?). Roger described a randomized algorithm that runs in $\log n$ rounds. The algorithm is local: a decision made at a given node depends only on actions of the nodes in its small neighborhood. He then proceeded to show that any algorithm for MIS requires at least $\log^* n$ rounds. The proof used Ramsey theory, which was a nice coincidence, given that a workshop on this topic was held in parallel. The lower bound in fact holds even for the line graph. Unfortunately (if you are a pessimist), for the line graph, there is a matching upper bound of $\log^* n$. Therefore, to improve the lower bound one needs a richer class of instances. Roger showed a construction of graphs for which one can show a lower bound of $\sqrt{\log n}$ or $\log \Delta$ (for a closely related problem of vertex cover). The graph was highly unusual, in that it was “highly symmetric” and “asymmetric” at the same time.

The next talk, by Pierre Fraigniaud, was on local distributed decisions (i.e., decision problems). An example of such problem is coloring validation: given a coloring, is it legal ? Other examples include: checking whether there is at most one marked node, consensus, etc. In general, one can define the notion of distributed language, which is a decidable collection of configurations. A configuration is accepted iff it is accepted by all nodes. In other words, the configuration is not accepted if someone says it is not accepted. Pierre presented several results on randomized algorithms for decision making, including a strong derandomization result (under certain conditions).

In the next session, Ning Xie talked about Local Computation Algorithms. Here the idea is that you are given the input, and problem at hand generates a large output. For example, the input is a graph and the task at hand is computing a maximal independent set (MIS). Let us assume that we want to output only one specific bit of the output. The question is whether we can do it in sublinear time, and in a way that is consistent, if we decide to read i bits of the output in some arbitrary fashion (i.e., think about the algorithm here is a query data-structure that outputs the desired bit). Since we need to be consistent across different queries, if we are going to use randomness, it needs to be compactly represented. To this end, one uses k-pairwise independent sequence of random bits, which can be specified compactly with a “few” random bits, and one can generate a long sequence implicitly that can “cheat” many algorithms. Secondary, to get a local computation, we need to be able to break up the input quickly into small fragments, such that the fragment that defines the desired output (i.e., it contains the vertex we need to output if it is in the MIS or not). The main idea is now to use Beck’s constructive version of the Lovasz Local Lemma. For example, you run a randomized MIS algorithm (parallel version) for a small number of iterations, and then you run a greedy algorithm on each remaining connected component. The randomized algorithm here chooses a vertex $v$ to the independent set with probability $1/2d$ ( $d$ is the degree in the given regular graph), and insert it if there are no collisions. After $O(d \log d)$ iterations, one proves that each remaining connected components is of size $O( \log n)$ with high probability. Thus, we can simulate this algorithm locally given a query vertex, and run on the relevant connected component directly, getting a sublinear running time.

Yuichi Yoshida talked about constant-time approximation algorithms. He started from recalling the result of Raghavendra who showed that if the Unique Games Conjecture is true, then for every constraint satisfaction problem (CSP), the best approximation ratio is attained by a certain simple semidefinite programming and a rounding scheme for it. He then showed that similar results hold for constant- time approximation algorithms in the bounded-degree model. He obtained the results in three steps. First, he showed that for every CSP, one can construct an oracle that serves an access, in constant time, to a nearly optimal solution to a basic LP relaxation of the CSP. Using the oracle, he then showed a constant-time rounding scheme that achieves an approximation ratio coincident with the integrality gap of the basic LP. Finally, he gave a generic conversion from integrality gaps of basic LPs to hardness results.

The last talk before lunch was by Vladimir Braverman. He focused on the following class of streaming problems: given a function G, estimate a statistic that is equal to the sum, over all i, of terms $G(m_i)$, where $m_i$ is the number of times an element $i$ appears in the stream. Alon,Matias and Szegedy asked for which functions G it is possible to approximate this statistic using a single pass over the data and using poly-logarithmic memory. Vladimir showed a precise characterization for all monotonically increasing functions $G$ such that $G(0)=0$. He also introduced the method of recursive sketching that can be used, e.g., for approximating frequency moments.