Alas! Sorry for the delay, but November was a good month with five seven papers. We missed a few papers from September, so please look at the updated post for September as well. (Update: Thanks to Omri Ben-Eliezer and an anonymous poster for pointing out two missed papers.)

From Local to Robust Testing via Agreement Testing, by Irit Dinur, Tali Kaufman, and Noga Ron-Zewi (ECCC). Consider a code, which is simply a subset of \(C \subseteq \mathbb{F}^n_q\). (Typically, we think of linear codes, which form a linear subspace.) The study of locally testable codes is a rich area. Consider an input \(x \in \mathbb{F}^n_q\). A local tester for code/property \(C\) queries, according to some distribution, a subset \(K\) of \(Q\) coordinates in \(x\), and rejects if the “view” \(x|_K\) is inconsistent with any codeword. The rejection probability should be proportional to the distance of \(x\) to \(C\), denoted \(dist(x,C)\). A robust tester demands the average distance of \(x|_K\) to the corresponding property \(C|_K\) must be proportional to \(dist(x,C)\). This is a much stronger demand than that of just local testing. The main result is local testability implies robust testability for the special class of lifted codes. The proof goes via agreement testing, where an algorithm gets access to some fragments of \(x\), and must decide if these fragments are consistent with a codeword.

Testing local properties of arrays, by Omri Ben-Eliezer (ECCC). Consider a function \(f:[n]^d \to \Sigma\), where \(\Sigma\) is finite. Now, suppose we define a property \(\mathcal{P}\) with respect to a set of forbidden \([k]^d\) (consecutive) subarrays. Such a property is called \(k\)-local. The inspiration for this work is a line of research on testing of image properties. Note that for \(k=2,3\), this notion subsumes a number of properties, such as monotonicity, \(c\)-Lipschitz, submodularity, convexity, etc. The main result is a one-sided, non-adaptive tester for all such properties. Ignoring \(\epsilon, k\) dependencies, the query complexity is \(O(\log n)\) for \(d=1\) and \(O(n^{d-1})\) for \(d > 1\). Remarkably, there is no dependence on the alphabet size \(|\Sigma|\). Moreover, the bound above is optimal for one-sided, non-adaptive testers. The basic idea to pick blocks of various sizes, and query all points on the boundary. Then, the tester can determine (by sort of brute force search) if this is consistent with some function in \(\mathcal{P}\). The key is to prove that for a function that is far from \(\mathcal{P}\), there are many blocks that cannot be consistent with \(\mathcal{P}\).

Erasures vs. Errors in Local Decoding and Property Testing, by Sofya Raskhodnikova, Noga Ron-Zewi and Nithin Varma (ECCC). The main theme of this paper is the notion of erasure-resilient testing. Consider property \(\mathcal{P}\). Suppose \(\alpha\)-fraction of the coordinates of input \(x\) is hidden. Thus, queries to these coordinates of \(x\) return nothing. Our aim is to accept if there is some “filling in” of the hidden coordinates that make \(x\) satisfy \(\mathcal{P}\), and reject if for all fillings, \(x\) remains from from \(\mathcal{P}\). If \(\alpha = 0\), this is standard property testing. Suppose there exists an \((\alpha, \alpha+\epsilon)\)-tolerant tester for \(\mathcal{P}\). (I’m fudging factors a bit here for readability.) We get an \(\epsilon\)-tester with \(\alpha\)-fraction of erasures, by simply filling \(x\) in arbitrarily. So this model is in between vanilla and tolerant testing. The main result is a separation. There is a property that is constant-query testable under erasures, but requires \(n^{\Omega(1)}\) queries to tolerant test (with the above parameters). One of the main technical results is a list decoder for the Hadamard code that can tolerate erasures of any \(\alpha \lt 1\).

Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions on Hypergrids, by Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri (ECCC). Consider monotonicity testing of Boolean functions of the hypergrid, \(f:[n]^d \to \{0,1\}\). It is known that there are \(O(d)\) testers with complexity independent of \(n\), while for \(n=2\), there are \(o(d)\) testers. The main result is a tester with both these properties. The paper gives an \(O(d^{5/6})\) tester for such functions. The main technical ingredient is a domain reduction theorem. Consider restrictions of \(f\) to a uniform random \([poly(d\epsilon^{-1})]^d\) hypergrid. The paper proves that if \(f\) is \(\epsilon\)-far from monotone, then (with high probability) so is the restriction. Thus, for the purposes of monotonicity testing, one can simply assume that \(n = poly(d)\). This gives a black-box method to get testers independent of \(n\).

On the Testability of Graph Partition Properties, by Yonatan Nakar and Dana Ron (ECCC). Consider property testing on dense graphs. The seminar result of Goldreich-Goldwasser-Ron studies graph partitioning properties. Such a property is defined as follows. Fix constant \(k\). We wish to partition the vertices of graph \(G\) into \(V_1, V_2, \ldots, V_k\). For each \(i\), \(|V_i|/n \in [\rho^L_i, \rho^U_i]\). Furthermore, for each \(i, j\), the number of edges between \(V_i, V_j\) must be in \([\rho^L_{i,j}n^2, \rho^U_{i,j}n^2]\). (All the \(\rho\)s are parameters of the property.) This subsumes properties like \(k\)-colorability, and the classic result is a \(poly(1/\epsilon)\)-tester for these properties. Note that the edge conditions are absolute, with respect to \(n^2\), and not with respect to \(|V_i|\cdot |V_j|\). This paper allows for relative bounds of the form \([\rho^L_{i,j}|V_i|\cdot |V_j|, \rho^U_{i,j}|V_i|\cdot |V_j|]\). This is far more expressive, subsuming properties like having large cliques, or large complete bipartite graphs. One of the main results is a (two-sided) \(poly(1/\epsilon)\) tester for all such properties. Furthermore, there is a characterization of such properties that are one-sided testable in \(poly(1/\epsilon)\) queries. For such properties, it is proven that the density conditions (between \(V_i, V_j\)) must either be unconstrained or have \(\rho^L_{i,j} = \rho^U_{i,j}\) be either 1 or 0.

Limits of Ordered Graphs and Images, by Omri Ben-Eliezer, Eldar Fischer, Amit Levi, and Yuichi Yoshida (arXiv). The theory of graph limits is a deep topic, with connections to property testing, regularity lemmas, and analysis of real-world networks. Roughly speaking, consider a sequence \(\{G_n\}\) of graphs where the (relative) frequency of any fixed subgraph converges. Then, we can define a limit of the graphs, called a graphon, which is a measurable function \(W:[0,1]^2 \to [0,1]\). This paper discovers appropriate limits of ordered graphs. Note that images can be represented as ordered graphs. An ordered graph is a symmetric function \(G:[n]^2 \to \{0,1\}\) (with the trivial automorphism group). The graphon definitions and limits do not generalize here. There is a sequence of ordered graphs where the ordered subgraph frequencies converge, but one cannot associate any graphon as the limit. This paper discovered a new object called an orderon, which is a function \(W:([0,1]^2)^2 \to [0,1]\). Orderons can be shown to be the limits of sequences of ordered graphs.

Two Party Distribution Testing: Communication and Security, by Alexandr Andoni, Tal Malkin, and Negev Shekel Nosatzki (arXiv). This paper gives a new take on distribution testing. Suppose Alice and Bob have each have access to \(t\) samples from (unknown) distributions \(p\) and \(q\) respectively. Their aim is to distinguish \(p = q\) from \(\|p-q\|_{TV} > \epsilon\). How much communication is required? In the standard setting, it is known that \(n^{2/3}\) (ignoring \(\epsilon\)) is necessary and sufficient. In the communication setting, the bound turns out to basically be \(\Theta((n/t)^2)\). Observe how for \(t=n^{2/3}\), the communication is \(n^{2/3}\) (saying that Alice is simply going to send all her samples to Bob). But for larger \(t\), the communication decreases. Since Alice can learn more about her distribution, she can use sketching techniques to reduce her communication. There is an analogous result for testing independence of two distributions. Furthermore, one can even require these protocols to be secure, so Alice and Bob learn nothing about each others samples (other than the final answer).