Happy New Year! This post covers the final property testing results for 2023. We have just two three papers, one on group testing, a new bound on sample-based testers, and a distribution testing result over higher dimensions.

On Testing Group Properties by Oded Goldreich and Laliv Tauber (ECCC). Group testing is a classic problem going back to the early days of property testing. We are given access to a “multiplication table” \(f: [n]^2 \to [n]\). Each element in \([n]\) is (supposedly) an element of a group, and \(f(i,j)\) is the product of elements \(i\) and \(j\). Our aim is to determine, in the property testing sense, whether \(f\) is the multiplication table of a group. The earliest result, from the seminal Spot-checkers paper, gave an \(\widetilde{O}(n^{3/2}/\varepsilon)\) time tester (where \(\varepsilon\) is the proximity parameter). This paper significantly improves that classic bound with a one-sided \(\widetilde{O}(n/\varepsilon)\) tester. Moreover, this tester can be adapted for testing of \(f\) is Abelian. The result is obtained by a series of testers, starting from extremely simple (yet time inefficient) to more complex versions. The best known lower bound is just \(\Omega(\log n)\), and that leaves a tantalizing (and wide open) gap to be reduced.

A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification by Marcel Dall’Agnol, Tom Gur, and Oded Lachish (arXiv). One of the powers of property testers is their choice of query. This is unlike the typical setting in learning, where one only gets access to random samples (or evaluations). Sample-based testers were defined to bridge this gap; so it is a property tester that only has access to (evaluations of) uniform random domain points. A sample-based tester simply checks if the sample is consistent with the property. It is natural to ask if the existence of a (vanilla) property tester implies the existence of a sample based tester. For the simplest setting, consider a \(q\)-query non-adaptive tester for some property \(\mathcal{P}\). One can visualize this as a collection of query sets of size \(q\) in a universe of size \(n\) (the domain). Naively, one might hope that with a \(q\)-way collision argument, a random sample of size \(O(n^{1-1/q})\) would contain a query set, yielding a sample based tester. Previous work showed that, for any property with a \(q\)-query non-adaptive tester, there is a sample-based tester with complexity \(O(n^{1-1/(q^2\log q)})\). Remarkably, this work gives such a bound for even adaptive testers (the best previous bound was \(O(n^{1-1/\exp(q)})\)). The result is placed in a broader framework of robust local algorithms, which subsume \(q\) query property testers, locally decodable codes (LDC), and MA proofs of proximity.

Testing Closeness of Multivariate Distributions via Ramsey Theory by Ilias Diakonikolas, Daniel M. Kane, and Sihan Liu (arXiv). (Missed from last month. -Ed) This paper considers distribution testing where the universe is \(\mathbb{R}^d\). The notion of closeness is called \(\mathcal{A}_k\) distance: we cover the universe with \(k\) axis-parallel rectangles, and “reduce” the distribution to a discrete universe of size \(k\). We then take TV-distance over these reduced distributions. When \(d=1\), the complexity of testing closeness was known to be \(\Theta(k^{4/5}/poly(\epsilon))\). For \(d > 1\), this paper gives the first non-trivial closeness testing result. The (optimal in \(k\)) bound achieved is \(\Theta(k^{6/7}/poly(\epsilon))\). Interestingly, there is a jump in the exponent on \(k\) from \(d=1\) to \(d=2\), but no jump for larger \(d\).