After an empty month, the engines of PTReview are roaring back to life with a fresh batch of papers for this month’s edition. In total, we have four papers that are sure to pique your interest. It’s been an action-packed month with a diverse range of topics covered in the featured papers. The first paper delves into new variations in distribution testing, while the second paper discusses optimal testers for Bayes Nets. The third paper focuses on optimal tolerant junta-testers, and the final paper presents a cool monotonicity tester over hypergrids.
Distribution Testing Under the Parity Trace by Renato Ferreira Pinto Jr and Nathaniel Harms (arXiv) The featured paper considers the classic setup in distribution testing with a twist. To explain the results, let me introduce the framework considered in this work. Consider distributions supported over \([n]\). Suppose I want to design distribution testers where instead of obtaining samples in the usual way, I first obtain an ordered list of samples, I store it in a sequence \(S\) and only the least significant bit of each element of \(S\) is made available to your distribution testing algorithm. This is called a parity trace. Note that with this access model, suddenly a bunch of standard tasks become non-trivial. To take an example from the paper, you can no longer distinguish between the uniform distribution supported on \(\{1,2, \ldots, n\}\) and the uniform distribution supported on \(\{n+1, n+2, \ldots 2n\}\) in this access model. Nevertheless, the paper shows, you can still obtain testers which require only sublinear number of accesses for testing uniformity in this model.
Another cool feature of this big paper is an unexpected foray into the trace reconstruction literature from a property testing viewpoint. I wish I understood the formal connection better to describe a bit more about it. But for now, let me leave that as an appetizer which (hopefully) encourages you to take a look at the paper.
New Lower Bounds for Adaptive Tolerant Junta Testing by Xi Chen and Shyamal Patel (arXiv) If you are a regular here on the PTReview corner, you are probably no stranger to the tolerant junta testing problem. As a corollary to the main result, the paper in question proves a lower bound of \(k^{\Omega(\log k)}\) queries on any adaptive algorithm that wishes to test whether the input function \(f\) is \(\varepsilon_1\) close to being a \(k\)-junta or whether it is \(\varepsilon_2\)-far \(\left(\text{where } \varepsilon_2 \geq \varepsilon_1 + \displaystyle\frac{1}{poly(k)}\right)\). Indeed, another remarkable achievement of the paper is that it achieves a superpolynomial separation between non-tolerant versions and the tolerant versions of any natural property of boolean functions under the adaptive setting.
Near-Optimal Degree Testing for Bayes Nets by Vipul Arora, Arnab Bhattacharyya, Clément L. Canonne (our own!) and Joy Qiping Yang (arXiv) This paper continues a line of investigation which a subset of the authors were a part of (which we also covered in our News for April 2022). Let us remind ourselves of the setup. You are given a probability distribution \(\mathcal{P}\) supported over the Boolean Hypercube. Suppose \(\mathcal{P}\) can be generated by a Bayseian Network. You may think of a Bayesian Network as a DAG where each vertex tosses a coin (with different heads probabilities). The question seeks to test whether \(\mathcal{P}\) admits a sparse Bayesian Net (in the sense of each vertex having small in-degree). The main result of the paper gives an algorithm for this task which requires \(\Theta(2^{n/2}/\varepsilon^2)\) samples. The paper also proves an almost matching lower bound.
A \(d^{1/2+o(1)}\) Monotonicity Tester for Boolean Functions on \(d\)-Dimensional Hypergrids by Hadley Black, Deeparnab Chakrabarty and C. Seshadhri (again, our own!) (arXiv) Again, the problem of monotonicity testing of boolean functions hardly requires any detailing to the regular readers of PTReview. As you can see in our News from November 2022 there were two concurrent papers mulling over this problem over the hypergrid domain. The featured paper is the result of a dedicated pursuit by the authors and the key result is what the title says. Namely, you can test monotonicity with a number of (non-adaptive, one-sided) queries that has no dependence on \(n\).