We’re now back to our regular cadence of 4+ monthly papers on property testing and sublinear time algorithms. July brings us a new sublinear PageRank computation and numerous results on our trending topics of distribution and monotonicity testing. Without further delay, let’s see the July spread.

Estimating Single-Node PageRank in \(\widetilde{O}(\min(d_t,\sqrt{m}))\) Time by Hanzhi Wang and Zhewei Wei (arXiv). PageRank is one of the most important quantities computed on graphs, especially in today’s networked world. Consider an undirected graph \(G = (V,E)\). The PageRank value of vertex \(t\) is the probability that a short random walk, starting from the uniform distribution, reaches the vertex \(t\). (Ok ok, I’m fudging details, but this is close enough to the truth.) The aim is to estimate this probability to within additive error \(O(1/n)\), where \(n\) is the number of vertices. A standard simulation would give an \(O(n)\) time algorithm; can we do sublinear in graph size? Previous work (which actually has implementations!) has led to \(O(\sqrt{n\cdot d_t})\) for undirected graphs [LBGS15] and (roughly) \(O(n^{2/3} d^{1/3}_{max})\) for all graphs [BPP18]. Here, \(d_t\) is the degree of vertex \(t\) and \(d_{max}\) is the maximum degree. This paper gets a bound of \(\widetilde{O}(\min(d_t,\sqrt{m}))\). A lower bound is still open for the fundamental problem! (A nice problem for any students reading…?)

Directed Poincare Inequalities and \(L_1\) Monotonicity Testing of Lipschitz Functions by Renato Ferreira Pinto Jr. (arXiv, ECCC). We all (or at least me) love monotonicity testing. The paper studies the continuous version, where \(f:[0,1]^n \to \mathbb{R}\). To have a reasonable notion of distance and testers, we will require functions to be differentiable and \(L\)-Lipschitz. We measure distance using \(\ell_1\) distance, so the distance between \(f,g\) is \(\int_{[0,1]^n} |f-g| d\nu\) (where we integrate over the uniform measure) [BRY14]. To access \(f\), we are also provided a “derivative oracle”: given a point \(x\) and a direction \(\vec{v}\), we can query the directional derivative along \(\vec{v}\) at \(x\). One of the key insights in (discrete, Boolean) monotonicity testing is the connection to directed isoperimetric inequalities. These inequalities are directed versions of classic inequalities that relate boundaries (or gradients) to volumes. For \(L\)-Lipschitz functions, the classic Poincare inequality states that \(E[\|\nabla f\|_1] \geq \textrm{var}(f)\), where \(\nabla f\) is the gradient and \(\textrm{var}(f)\) is (up to constant factors) the distance to being constant. This paper proves the directed version \(E[\|\nabla^- f\|_1] \geq \varepsilon(f)\). Roughly speaker, \(\nabla^-\) is the “negative gradient” (\(min(\nabla f, 0)\)) and \(\varepsilon(f)\) is the \(L_1\)-distance to monotonicity. This result directly yields a \(O(n/\varepsilon)\) query tester for monotonicity. The paper asks the tantalizing question: can we do better?

A Strong Composition Theorem for Junta Complexity and the Boosting of Property Testers by Guy Blanc, Caleb Koch, Carmen Strassle, and Li-Yang Tan (arXiv). It is best to go backwards in discussing this paper, starting from the implications and going to the core results. The problem at hand is the classic one of junta testing. Given \(f:\{0,1\}^n \to \{0,1\}\), distinguish if \(f\) only depends on \(r\) variables (an \(r\)-junta) or is \(\varepsilon\)-far from having that property. This problem is well studied, has optimal (efficient) testers, and even has results in the distribution-free setting. In the latter setting, there exists some (unknown) distribution \(\mathcal{D}\) on the domain according to which distance is defined. The tester can access to queries according to \(\mathcal{D}\). The clarity of junta testing disappears when we consider tolerant testing: can we distinguish \(f\) is (say) \(1/4\) close to an \(r\)-junta from being \(1/3\)-far (where distances are measured according to \(\mathcal{D}\))? A remarkable consequence of this paper is that this tolerant testing version is unlikely to have a \(poly(n)\) time algorithm. (Note that the sample complexity might still be small.) The main tool is a composition theorem that gives reductions between low \(\varepsilon\) testers and constant \(\varepsilon\) testers. The details are intricate, but here’s the gist. Suppose we can construct composing functions \(g\) such that the distance to “junta-ness” of \(g \circ f\) is much larger than the distance of \(f\). Then a tester (that can only deal with large \(\varepsilon\)) on \(g \circ f\) can effectively property test \(f\). (Obviously, I’m greatly oversimplifying and mischaracterizing. So go read the paper!)

The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination by Clément L. Canonne, Samuel B. Hopkins, Jerry Li, Allen Liu, and Shyam Narayanan (arXiv). Consider the fundamental hypothesis testing problem of Gaussian testing. We wish to distinguish the \(d\)-dimensional, zero-mean, unit covariance Gaussian \(\mathcal{N}(0,I)\), from the “shifted” version \(\mathcal{N}(\mu,I)\), where \(\mu\) is a vector of length at least $latex  \alpha$. Existing results give a simple algorithm using \(\Theta(\sqrt{d}/\alpha^2)\) samples. Suppose there is an adversary who can corrupt samples. The adaptive adversary can look at the samples generated, and arbitrarily change an \(\varepsilon\) fraction of entries. The weaker, oblivious adversary can also arbitrarily change an \(\varepsilon\) fraction of entries, but cannot look at the samples generated. Can we perform Gaussian testing in this setting? A previous result gave an optimal bound for adaptive adversaries [N22]. This paper gives the optimal sample complexity bound for oblivious adversaries. The expression is somewhat complicated. But the punchline is that for many regimes of parameters \(d, \alpha, \varepsilon\), the oblivious adversary is strictly weaker. Meaning, there is a testing algorithm (against an oblivious adversary) whose sample complexity is strictly less than the optimal bound against adaptive adversaries. This comes as a surprise, because in typical distribution testing settings, these adversaries are basically equivalent.

Uniformity Testing over Hypergrids with Subcube Conditioning by Xi Chen and Cassandra Marcussen (arXiv). A problem of generalizing from hypercube to hypergrids, an issue I have much obsessed over. Consider the problem of uniformity testing, where the domain is the hypergrid \([m]^n\). We wish to test if a distribution \(\mathcal{D}\) over the hypergrid is uniform. Unlike the standard distribution testing setting, the domain size is exponentially large. To aid us, we can perform conditional sampling: we can select any sub-hypergrid, and get samples from \(\mathcal{D}\) restricted to this sub-hypergrid. Previous work solved this problem for the hypercube domain (when \(m=2\)), by providing a tester with sample complexity \(O(\sqrt{n}/\varepsilon^2)\) [CCKLW22]. The previous work did not work for any other hypergrid (even \(m=3\)). This paper gives the first solution for uniformity testing on hypergrids with a tester of sample complexity \(O(poly(m)n/\varepsilon^2)\). The dependence on \(m\) has to be at least \(\sqrt{m}\), from existing results. One of the important tools is getting robust versions of classic isoperimetric inequalities over the hypergrid. An important open question is to determine the optimal dependence on \(\mathcal{m}\).

Learning and Testing Latent-Tree Ising Models Efficiently by Davin Choo, Yuval Dagan, Constantinos Daskalakis, and Anthimos Vardis Kandiros (arXiv). Depending on your standpoint, one may or may not consider this a “sublinear time” paper (it does not show that testing \(\ll\) learning). But given the interest in distribution testing, I think it’s germane to our blog. We have a high-dimensional distribution \(\mathcal{D}\) over \((x_1, x_2, \ldots, x_n)\). Without any assumption, learning (or even identity testing) requires exponential in \(n\) many samples. This paper assumes that \((x_1, x_2, \ldots, x_n)\) is generated from a latent-tree Ising model. There is a tree where each node is associated with a number (think \(x_i\)), and the joint distribution satisfies some dependencies according to the edges. We only observe the values of the leaves; hence, the term “latent” model. The main result shows that identity testing can be done in with polynomial in \(n\) samples. The authors also prove that one can learn the distribution in (albeit larger) \(poly(n)\) samples.