The Sublinear Algorithms Workshop, JHU, January 2016

Oded's notes

The Sublinear Algorithms Workshop, which took place on January 7-9, 2016, at Johns Hopkins University, was one of the most enjoyable and inspiring workshop I have ever attended. Organized by Vladimir (Vova) Braverman, Piotr Indyk, Robert (Robi) Krauthgamer, and Sofya Raskhodnikova, it seems that its success rooted in the decision to open the workshop to whoever is interested in its contents. This led to an exceptionally high number of attendees (in comparison to a workshop), dominated by a large number of eager-to-learn graduate students, creating an atmosphere of pure interest and great engagement.

A word about the location: The JHU campus is beautiful. It has a beautiful collection of buildings, which look great both from outside and inside. For example, the public rooms at Gilman are amazing, and the auditorium in which the workshop took place is also very nice. Also a word of thanks to the careful local organization orchestrated by Vova and played out by him and his student, Nikita Ivkin.

The following collection of comments refers to some of the talks I have attended. As usual, for me, I did not attend all talks, due to the need to refresh myself from time to time. My comments are quite laconic, and one may want to look at the abstracts available from the workshop webpage.

Christian Sohler: Testing Cluster Structure of Graphs

I am very supportive of the idea of viewing clusters as "well connected" components of a graph, where well connectivity is viewed as a gap between the internal conductance of the component (as an induced subgraph) and the conductance of the cut defined by the component. The corresponding testing task generalizes the one of testing expansion, and consists of distinguishing the case that the graph can be k-partitioned in a way that satisfies a predetermined pair of conductance thresholds (i.e., lower bound on internal conductance and upper bound on external conductance) and the case that the graph is far from having a k-partition that satisfies a (possibly relaxed) pair of such thresholds.

Artur Czumaj: Testing Directed Graphs

When studying testing properties of directed graphs, in a model analogous to the bounded-degree model of undirected graphs, one should make two (orthogonal) distinctions. The first distinction is between properties of the directed graph, which are sensitive to the orientation of edges, and properties of the underlying undirected graph (i.e., the undirected graph obtained from the directed graph when ignoring the orientation of edges). The second distinction is between a model in which the tester can make queries regarding both out-going and in-coming edges and a model in which one can only make queries about outgoing edges.

This work studies the gap between these two models, showing that if a property can be tested with a constant number of queries in the bi-directional query model, then it can be tested in a sublinear number of queries in the uni-directional query model. The transformation des not preserve one-sided error probability, and this is inherent, since there are properties that have a constant-query one-sided error tester in the first model but no sublinear-query one-sided error tester in the second model.

Ilias Diakonikolas: Testing Structured Distributions

I like this work very much: It presents a very appealing framework for deriving testers for properties of distributions. It suggests to "flatten" the given distributions such that their L2-norm is utmost small, while preserving their distance to the property in question, and then apply a basic tester that has optimal complexity for distributions if small L2-norm. Using this transformation, one can reduce various property testing problems to the corresponding case (of small L2-norm), offering a unified and simple way of establishing many known results. I plan to use this approach when teaching the subject of testing properties of distributions.

Oded Goldreich: Testing Dynamic Environments

I tried to promote this new direction of research by focusing on the model and on what makes it different from standard testing problems. The tested object is an evolution of a sequence of $d$-dimensional arrays and the property in question is whether this sequence represents the evolution of a ($d$-dimensional) cellular automata according to a predetermined rule. The key aspect that makes this testing task different from testing a property of a $(d+1)$-dimensional is that the tester (as an observer) cannot "go back in time".

Stephen Chestnut: The space complexity of streaming sums

This works refers to the space complexity of computing the sum of a $g$-function of the frequencies (in the stream). While it is known that $g(x)x^c$ admits a polylog space algorithm if and only if $c\leq 2$, this work seems and almost achieves a characterization of all $g$'s for which such algorithms exist. One of the necessary conditions requires a growth rate that is at most (nearly) quadratic, and other conditions mandate a "reasonable" behavior of $g$.

Ronitt Rubinfeld: Local Algorithms for Sparse Spanning Graphs

The framework of local computational algorithms (LCAs) generalizes several types of tasks. It refers to algorithms that given oracle access to one object, captured by a function $f$, provided oracle access to a related object, denoted $g$, such that each query to $g$ can be answered by making few queries to $f$. The function $g$ need not be uniquely determined by $f$, but it should reside in a set of admissible solutions that is determined by $f$. That is, given oracle access to $f$, the algorithm such answer according to any $g$ that is in a predetermined set of valid solutions for $f$. In other words, for a predetermined relation $R$, given $f$ one should answer according to any $g$ such that $(f,g)\in R$. The algorithm is allowed to be randomized, but for every possible sequence of coin tosses $r$, all possible queries must be answered according to the same $g=g_r$. Since this is a search problem, with possibly more than one valid solution for every input, error reduction is not necessarily possible, and so it is required to specify the error probability of the reduction (in case such is allowed).

Property testing is captured as a very degenerated case in which $g$ is a single bit. But this framework is aimed at capturing cases in which $g$ is of size comparable to the side of $f$. One such case is that of "local reconstruction", where for a fixed property $\Pi$, given $f$ that is close to $\Pi$, one is required to answer according to $f'\in\Pi$ that is close to $f$. The current work focuses on finding a relatively sparse spanning subgraph of a given graph. That is, the set of valid solutions for the connected $n$-vertex graph $G$, is the set of all connected subgraph of $G$ that contain all $n$ vertices of $G$ but only $(1+\esp)n$ edges.

Noga Ron-Zewi: High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity

Research in 1990-2010 aimed at codes (of constant relative distance) that support testers (and local decoders) of constant-query complexity and focused at maximizing their rate (which is sub-constant). It is most fitting for the current workshop to present a work that focuses on minimizing the query complexity of testing (and locally decoding) codes of constant rate. Indeed, the query complexity has been known to be sublinear, but the breakthrough is in getting below a constant power of the length. For testing, they obtain quasi-polylogarithmic (i.e., $(\log n)^{\log\log n}$) query complexity, and for local decoding the bound is $\exp(\sqrt(\log n))$.

Grigory Yaroslavtsev: L-p testing

While property testing focuses on the Hamming distance, viewed here as a =E2=80=9CL0-norm=E2=80=9D, a more general distance measure is defined as $\frac{\|f-g\|_p}{\|1\|_p}$, and the case of $p=1$ is indeed the most appealing one. Using relations among norms, one immediately obtain various relations among the complexity of testing with respect to different norms. The main result is that, for the L1-norm, $\e$-testing monotonicity on the line is possible in $O(1/\eps)$ queries, whereas under the Hamming distance a logarithmic (in the length of the line) complexity is required.

Dana Ron: Approximately counting triangles in sublinear time

When only allowing neighbor (and degree) queries, this task requires linear (in the number of vertices) many queries. Seeking sub-linear algorithms, this work also allows adjacency queries (as in the model of testing properties of general graphs). Then, the query complexity is essentially $O((n/t^{1/3})+\min(m,m^{3/2}/t))$, where $t \min(n^a,m^b)$, for $a,b\geq1$, the expression simplifies to $O(n^{1-(a/3) + m^{1.5-b}} = O(n^{2/3}+m^{1/2})$. A non-trivial warm-up refers to the case in which one seeks to improve the approximation factor from some large constant to a smaller constant, when given access also to a devise that samples edges uniformly at random and to an oracle that returns the number of triangles in which the queried edge participates.

David Woodruff: Beating CountSketch for Heavy Hitters in Insertion Streams

This work presents another setting in which improved randomized algorithms are obtained by avoiding a straightforward union bound. Instead of reducing the error probability so to afford such a union bound, this work reduces the gap (between the sought object and the rest) for which the problem can be solved.

Alexandr Andoni: Sketching and Embedding are Equivalent

Sketching is viewed as a communication problem in which each party sends a "sketch" of its input to a referee, who then distinguishes the case that the original inputs are close from the case they are far, where the "distortion" is the gap between close and far. This formulation suggests that the problem can be solved by embedding the original inputs in a low dimensional space, provided that the embedding has the adequate distortion. This work asks whether this sufficient condition is necessary, and obtains a positive answer using embedding to the $L_p$-normed space for any constant $p<1$. Obtaining such result for embedding into $L_1$-norm would resolve a known open problem in geometry. Nevertheless, the current result allows to derive lower bounds on sketching by relying on impossibility results regarding embedding (e.g., for sketching that preserves the Earth-Mover-Distance).

The original program

See a word file.

Back to list of Oded's choices.