Apologies, dear readers for the delay in getting out this month’s post. This month we had three papers — all on testing properties of graphs! (EDIT: Updated later) four papers: three on property testing problems on graphs and the last one on testing convexity. One of the featured papers this month revisits the problem of testing the properties of directed graphs and comes back with a happy progress report. Alright, let’s dig in.

A Distributed Conductance Tester Without Global Information Collection by Tugkan Batu, Chhaya Trehan (arXiv) One of the classic questions in property testing considers the task of testing expansion. Here, you are interested in knowing whether the input graph has conductance at least \(\alpha\) or it is far from having conductance at most \(\alpha^2\). On a parallel track, we recall that thanks to the classic work of Parnas and Ron, we know there are connections between distributed algorithms and graph property testing. Meditating on these connections led to the emergence of distributed graph property testing as an active area of research. The featured paper considers the task of testing expansion in the distributed framework. The algorithms presented give a distributed implementation of multiple random walks from all vertices, and controls the congestion of the implementation. In particular, this leads to a \(O(\log n/\alpha^2)\) round expansion-tester. In a first attempt at such an implementation, you might note that you need to track how well short random walks mix when started from a bunch of randomly chosen vertices. This seems to require maintaining some global state/global aggregate information. One of the important features of their algorithm (as mentioned in the title) does away with the need to maintain such global states. As a closing remark, I note the algorithm presented in this paper does not require the graph to be bounded degree.

Testing versus estimation of graph properties, revisited by Lior Gishboliner, Nick Kushnir, Asaf Shapira (arXiv) This paper considers the task of additively estimating the distance to a property \(\mathcal{P}\) of a dense graph. Let me set up some context to view the results in the featured paper by summarizing what was known before. One of the early important results in this area is the original result of Fischer and Newman which shows that any testable graph property admits a \(\pm \varepsilon\) distance approximation algorithm, which follows from the regularity lemma. However, the query complexity of the resulting algorithm is a Wowzer-style bound. Later, Hoppen et al., building upon tools from the classic work of Conlon and Fox, demonstrated that this bound of \(twr(poly(1/\varepsilon))\) also holds for testable hereditary properties. Fiat and Ron introduced a decomposition machinery that allowed them to decompose a “complex” property into a collection of simpler properties. They used this decomposition to estimate distances to a vast collection of graph properties. They also asked if it was possible to find a transformation using which one can bypass the blowup in query complexity incurred by Fischer and Newman for some rich class of graph properties. The featured paper proves that for a hereditary graph property, you can in fact get algorithms where the query complexity for distance estimation only grows as \(\exp(1/\varepsilon)\). Additionally, for every testable graph property, you can get distance estimators for that property whose query complexity only grows doubly exponentially in \(1/\varepsilon\) (as opposed to the tower bound earlier).

An Optimal Separation between Two Property Testing Models for Bounded Degree Directed Graphs by Pan Peng, Yuyang Wang (arXiv) Unlike undirected graphs, directed graph properties have not received as much attention in the property testing community. In a classic work, Bender and Ron considered two natural models for studying property testing on directed graphs. The first model is one where you can only follow the “out” edges or the so-called unidirectional model. In the other model, you are allowed to follow both the “out” edges and the “in” edges incident on the vertex which is also called the bidirectional model. The featured paper considers directed graphs where the in-degree and the out-degrees are both bounded in both of the models mentioned above. The graph is presented to you in the adjacency list format (tailored for the model you consider). The paper shows that even for the fundamental task of subgraph-freeness, the directed world has some interesting behavior with respect to the two models above. Let me showcase one of the catchy results from the paper which illustrates this separation nicely. Take a connected directed graph \(H\) with \(k\) source components. The paper shows that for sufficiently small \(\varepsilon\), testing whether a directed graph \(G\) is \(H\)-free or \(\varepsilon\)-far from being \(H\)-free requires \(\Omega(n^{1-1/k})\) unidirectional queries. On the other hand, in the bidirectional model, this can be done with a mere \(O_{\varepsilon, d, k}(1)\) number of queries.

(EDIT: Added later)

Testing Convexity of Discrete Sets in High Dimensions by Hadley Black, Eric Blais, Nathaniel Harms (arXiv) As the title suggests, this paper explores the problem of testing convexity. To understand the notion of convexity explored in the paper, consider the following setup: You call a set \(S \subseteq \{-1, 0, 1\}^n\) convex if there exists a convex set \(S’ \subseteq \mathbb{R}^n\) such that \(S = S’ \cap \{-1,0,1\}^n\). And you call a set \(S \subseteq \{-1,0,1\}^n\) far from being convex if for every convex \(T \subseteq \{-1,0,1\}^n\), you have \(|S \oplus T| \geq \varepsilon 3^n\). The paper shows that when you are allowed membership queries, you can test convexity non-adaptively with a one-sided error by issuing \(3^{O(\sqrt{n \log(1/\varepsilon)})}\) queries. Also, they prove an almost matching lower bound. Finally, with a lower bound of \(3^{\Omega(n)}\) when confined to using sample-based testers, authors provably demonstrate that membership queries indeed buy you some undeniable power for testing convexity in high dimensions.