May brought us a wealth of new papers, including four (!) on distributed property testing.
Distributed Property Testing for Subgraph-Freeness Revisited, by Orr Fischer, Tzlil Gonen, and Rotem Oshman (arXiv). This paper studies subgraph-freeness testing in the CONGEST model of distributed computation. This problem was previously studied — this paper provides a number of new algorithms, which either improve upon the running time of prior work or are the first non-trivial results for these problems. Some cases they study include testing for freeness of \(k\)-cycles, constant-size trees, and \(k\)-cliques. For the latter case, they prove that a dependence on \(\varepsilon\) is necessary.
Faster and Simpler Distributed Algorithms for Testing and Correcting Graph Properties in the CONGEST-Model, by Guy Even, Reut Levi, and Moti Medina (arXiv). This paper also studies graph property testing in the CONGEST model. There appears to be some overlap in problems with the previous paper, including testing subgraph-freeness for cycles and constant size trees. As the title suggests, they also study graph property correction in the case of \(k\)-cycles, and other properties such as bipartiteness.
K-Monotonicity is Not Testable on the Hypercube, by Elena Grigorescu, Akash Kumar, and Karl Wimmer (arXiv, ECCC). Recent work introduced the concept of \(k\)-monotonicity, where a function may switch value between \(0\) to \(1\) at most \(k\)-times on any ascending chain. This generalizes the common notion of monotonicity, which corresponds to \(k = 1\). Since \(1\)-monotonicity on the hypercube is testable in \(O(\sqrt{n})\) queries, it was conjectured that \(k\)-monotonicity may be tested in \(poly(n^k)\) queries. This paper disproves this conjecture, showing that even \(2\)-monotonicity requires a number of queries which is exponential in \(\sqrt{n}\).
The coin problem for product tests, by Chin Ho Lee and Emanuele Viola (ECCC). The coin problem asks, if \(f\) is a product of \(k\) functions on disjoint inputs of length \(n\) bits, what is the smallest \(\varepsilon\) such that \(f\) can distinguish between an input of \(m = nk\) fair bits versus an input of \(m\) \(\varepsilon\)-biased bits. This paper proves tight bounds in a few cases of interest — when the range of \(f\) is \(\{0, 1\}\) or \(\{\pm 1\}\), the answer is \(\Theta(1/\sqrt{n\log k})\), while if the range is the set of unit-norm complex numbers, the answer is \(\Theta(1/\sqrt{nk})\).
Distributed Testing of Conductance, by Hendrik Fichtenberger and Yadu Vasudev (arXiv). Another paper on testing in the CONGEST model — this one studies the problem of testing conductance. In particular, they give an \(O(\log n)\) round two-sided tester which distinguishes between graphs with conductance at least \(\Phi\) and graphs which are \(\varepsilon\)-far from having conductance at least \(\Omega(\Phi)\). They also prove a lower bound of \(\Omega(\log n)\), even in the (easier) LOCAL model.
On The Multiparty Communication Complexity of Testing Triangle-Freeness, by Orr Fischer, Shay Gershtein, and Rotem Oshman (arXiv). The final paper in May on distributed graph property testing — in contrast to the other papers, this paper considers multiparty communication complexity in the coordinator model. A graph is divided up among \(k\) players, and each player can only communicate with a coordinator and not each other. The authors show upper bounds on the communication, in both the vanilla and the simultaneous model (which allows only \(1\) round of communication). They also show a near-matching lower bound for simultaneous protocols on graphs of constant degree.
Exponentially Small Soundness for the Direct Product Z-test, by Irit Dinur and Inbal Livni Navon (ECCC). This paper studies the problem of direct product testing, in which one tests whether the output of a function on a coordinate depends only on the input to that coordinate (approximately). The authors investigate the Z-test of Impagliazzo, Kabanets, and Wigderson, and show that it achieves the optimal soundness of \(\varepsilon \geq \exp(-O(k))\).