**Direct sum testing – the general case**, by Irit Dinur and Konstantin Golubev (ECCC). Say a function \(f\colon \prod_{i=1}^d [n_i] \to \mathbb{F}_2\) is a direct product if it can be factored as \(f(x_1,\dots,x_d)=\sum_{i=1}^d f_i(x_i)\), where \(f_i\colon [n_i]\to\mathbb{F}_2\).

This paper provides a 4-query tester (i.e., a *proximity oblivious tester* (POT)) for the direct product property, reminiscent of (and relying on) the BLR linearity test: specifically, draw two subsets \(S,T\subseteq [d]\) and two inputs \(x,y\in \prod_{i=1}^d [n_i]\) u.a.r., and accept iff

\(f(x)+f(x_Sy)+f(x_Ty)+f(x_{S\Delta T}y) = 0\,.\)

The main theorem of the paper is to show that the probability that this simple test rejects is lower bounded (up to a constant factor) by the distance of \(f\) to direct-product-ness. (The authors also provide a different POT making \(d+1\) queries, but with a simpler analysis.)

**Finding monotone patterns in sublinear time**, by Omri Ben-Eliezer, Clément Canonne, Shoham Letzter, and Erik Waingarten (ECCC). Given a function \(f\colon [n]\to\mathbb{R}\), a *monotone subsequence* of size \(k\) is a \(k\)-tuple of indices \(i_1 < \dots <i_k\) such that \(f(i_j) < f(i_{j+1})\) for all \(j\). This work considers (non-adaptive) one-sided testing of monotone-subsequence-freeness, or, equivalently, the task of *finding* such a monotone subsequence in a function promised to contain many of them. (This, in particular, generalizes the problem of one-sided monotonicity testing, which is the case \(k=2\).) The main result is a full characterization of the query complexity of this question (for constant \(k\)): strange as the exponent may seem, \(\Theta_\varepsilon( (\log n)^{\lfloor \log_2 k\rfloor} )\) queries are necessary and sufficient. The proof relies on a structural dichotomy result, stating that any far-from-free sequence either contains “easy to find” increasing subsequences with increasing gaps between the elements, or has a specific hierarchical structure.

**Quantum Closeness Testing: A Streaming Algorithm and Applications**, by Nengkun Yu (arXiv). This paper is concerned with quantum distribution testing in the *local* model, which only allows a very restricted (albeit, as the author argues, more natural and easier to implement) type of measurements, and is particularly well-suited to a streaming setting. The main contribution of this paper is to show a connection to *classical* distribution testing, allowing one to obtain quantum distribution testing upper bounds from their classical distribution testing counterparts. In more detail, the paper shows that, from local measurements to two \(d\)-dimensional quantum states \(\rho,\sigma\), one can provide access to two classical distributions \(p,q\) on \(\approx d^2\) elements such that (i) \(\| p-q\|_2 \approx \|\rho-\sigma\|_2/d\) and (ii) \(\| p\|_2,\| q\|_2 = O(1/d)\).

Using this connection, the paper proceeds to establish a variety of upper bounds for testing several distribution properties in the local quantum model.

**Hard properties with (very) short PCPPs and their applications**, by Omri Ben-Eliezer, Eldar Fischer, Amit Levi, and Ron D. Rothblum (arXiv). Probably, the most significant takeaway from this work is a (largest possible) separation between standard and tolerant property testing. PCPPs (Probabilistically Checkable Proofs of Proximity) are the “NP” variant of property testing, where the tester is aided by a proof string. Consider property \(\mathcal{P}\). If \(x \in \mathcal{P}\), there must be a proof string that makes the tester accept (with probability 1). If \(x\) is far from \(\mathcal{P}\) (in the usual property testing sense), for any proof string, the tester must reject with sufficiently high probability. PCPPs have played a role in the classical constructions of PCPs, but have also found uses in getting a better understanding of property testing itself. And this paper shows how PCPP constructions can be used to get property testing separations. The main result in this paper is a property \(\mathcal{P}\) that (basically) requires \(\Omega(n)\) queries to “property test”, but has a PCPP system where the proof length is \(\widetilde{O}(n)\). (\(n\) is the input length.) The main construction uses collections of random linear codes. Significantly, these constructions show a strong separation between standard vs tolerant property testing, and standard vs erasure-resilient property testing. (The latter is a recent variant by Dixit et al, where certain parts of the input are hidden from the tester.) There is a property that is testable in a constant number of queries, but requires \(\widetilde{\Omega}(n)\) queries to test tolerantly (for any non-trivial choice of parameters). An analogous result holds for erasure-resilient testing.

**Distribution-Free Testing of Linear Functions on R^n**, by Noah Fleming and Yuichi Yoshida (arXiv). Linearity testing is arguably *the* canonical problem in property testing, yet there is still much to be learned about it. This paper considers functions \(f: \mathbb{R}^n \to \mathbb{R}\), and the *distribution-free setting*. (In this setting, distance is measured according is an unknown distribution \(\mathcal{D}\) over the input, and the tester can access samples from this distribution. For \(\mathbb{R}^n\), the “standard” distribution would the \(n\)-dimensional Gaussian.) The main result is that linearity testing can be done in the distribution-free setting with \(\widetilde{O}(1/\varepsilon)\) queries, assuming that the distribution is continuous. The primary technical tool, an interesting result in its own right, is that additivity \((f(x+y) = f(x) + f(y))\) can be tested in \(\widetilde{O}(1/\varepsilon)\) queries. The significance of the testing result is cemented by an \(\Omega(n)\) lower bound for sample-based testers.

**Sliding window property testing for regular languages** by Moses Ganardi, Danny Hucke, Markus Lohrey, Tatiana Starikovskaya (arXiv). Fix a regular language \(\mathcal{R}\). Consider the streaming model, and the basic question of recognizing whether the string (being streamed) is in \(\mathcal{R}\). Simple, you will say! Run the DFA recognizing \(\mathcal{R}\) in constant space. Now, suppose there is a sliding window length of \(n\). The aim is to determine if the past \(n\) symbols (the “active window”) form a string in \(\mathcal{R}\). Suprisingly (at least to me), there is a full characterization of the space required for randomized algorithms, and (depending on \(\mathcal{R}\)), it is either \(\Theta(1)\), \(\Theta(\log\log n)\), \(\Theta(\log n)\), or \(\Theta(n)\). In the interest of beating these lower bounds, suppose we wish to property test on the active window. It turns out the answer is quite nuanced. There are deterministic \(O(\log n)\)-space testers and randomized two-sided \(O(1/\varepsilon)\)-space testers for all regular languages. For randomized one-sided testers, there are multiple possibilities for the optimal space complexity, and there is a full characterization of these regular languages.

**A characterization of graph properties testable for general planar graphs with one-sided error (It’s all about forbidden subgraphs)** by Artur Czumaj and Christian Sohler (arXiv). Property testing of sparse graphs has been receiving more attention, but most results focus on the bounded degree setting. Unfortunately, many of these results break quite dramatically on sparse graphs with unbounded degrees. This paper focuses on property testing, within the class of unbounded degree planar graphs. (Meaning, the input is always assumed to be planar.) The results achieve a significant goal: as the title suggests, there is a complete characterization of properties that are constant-query testable with one-sided error. The easier part is in showing that all such properties can be reduced to testing \(H\)-freeness. The harder (remarkable) result is \(H\)-freeness can be tested in general planar queries with constant queries. (This is non-trivial even for triangle-freeness.) And, as is easy to conjecture but hard to prove, these results carry over for all minor-closed families. As a small indication of the challenge, most testers for bounded-degree graphs work by doing constant depth BFSes. When high degree vertices are present, this method fails, and we really need new ideas to deal with such graphs.

**Near Coverings and Cosystolic Expansion – an example of topological property testing** by Irit Dinur and Roy Meshulam (ECCC). In most algebraic settings, property testing results can be seen as local to global theorems. When do local constraints on a large object imply a global condition? This paper gives a topological instantiation of this phenomenon. We need to define the *cover* of a simplicial complex \(X\). For concreteness, think of a 2D simplicial complex \(X\), which is a hypergraph with hyperedges of size at most 3, where subsets of hyperedges are also present. A 2-cover is a simplicial complex \(X’\) with the following property. It has two copies of each vertex of \(X\). Each hyperedge of \(X\) must have two “corresponding” disjoint copies in \(X’\). Let the copies of vertex \(v\) be \(v_0, v_1\). Then, for every hyperedge (say) \((u,v,w)\) of \(X\), there must be two disjoint hyperedges in \(X’\) involving copies of the corresponding vertices. One can consider the property testing twist: if the neighborhoods of “most” vertices \(v\) in \(X\) satisfy these condition (with respect to the neighborhoods of the copies of \(v\) in \(X’\)), then is \(X’\) close to being a cover of \(X\)? Indeed, this paper proves that such a “property testing condition” holds iff \(X\) is a high-dimensional expander.

**Property testing of the Boolean and binary rank** by Michal Parnas, Dana Ron, and Adi Shraibman (arXiv). The Boolean rank of a matrix \(M\) is a fundamental quantity that appears in many lower bound constructions. (Recall that an \(n \times m\) Boolean matrix \(M\) has a rank \(r\) if \(M\) can be expressed as \(X \cdot Y\), where \(X \in \mathbb{F}_2^{n \times d}\) and \(Y \in \mathbb{F}_2^{d \times m}\).) In the real-valued setting, results show that one can property test rank in \(poly(d/\varepsilon)\) queries. This paper proves an analogous result for the Boolean rank. There is a surprise element here: over reals, the rank can be computed in polynomial time, and many of the geometric intuitions can be brought over to the property testing problem. On the other hand, the Boolean rank is NP-hard to compute exactly, yet we can still get a tester with \(poly(d)\) query complexity. The paper also gives results for *binary rank*. For the binary rank, we require the component matrices \(X, Y\) to be Boolean, but algebraic operations are over the reals. In the case, the tester has query complexity \(2^{2d}\) (with varying dependencies on \(\varepsilon\) for adaptive/non-adaptive testers). The intriguing open problem is whether \(poly(d)\)-query testers exist for binary rank.

]]>

**Testing convexity of functions over finite domains**, by Aleksandrs Belovs, Eric Blais, and Abhinav Bommireddi (arXiv). This paper studies the classic problem of convexity testing, and proves a number of interesting results on the adaptive and non-adaptive complexity of this problem in single- and multi-dimensional settings. In the single-dimensional setting on domain \([n]\), they show that adaptivity doesn’t help: the complexity will be \(O(\log n)\) in both cases. However, in the simplest two-dimensional setting, a domain of \([3] \times [n]\), they give a polylogarithmic upper bound in the adaptive setting, but a polynomial lower bound in the non-adaptive setting, showing a strong separation. Finally, they provide a lower bound for \([n]^d\) which scales exponentially in the dimension. This leaves open the tantalizing open question: is it possible to avoid the curse of dimensionality when testing convexity?

**Testing Isomorphism in the Bounded-Degree Graph Model**, by Oded Goldreich (ECCC). This work investigates the problem of testing isomorphism of graphs, focusing on the special case when the connected components are only polylogarithmically large (the general bounded-degree case is left open). One can consider when a graph is given as input, and we have to query a graph to test if they are isomorphic. This can be shown to be equivalent (up to polylogarithmic factors) to testing (from queries) whether a sequence is a permutation of a reference sequence. In turn, this can be shown to be equivalent to the classic distribution testing question of testing (from samples) whether a distribution is equal to some reference distribution. The same sequence of equivalences *almost* works for the case where there is no reference graph/sequence/distribution, but we only have query/query/sample access to the object. The one exception is that the reduction doesn’t work to reduce from testing distributions to testing whether a sequence is a permutation, due to challenges involving sampling with and without replacement. However, the author still shows the lower bound which would be implied by such a reduction by adapting Valiant’s proof for the distribution testing problem to this case.

**Learning Very Large Graphs with Unknown Vertex Distributions**, by Gábor Elek (arXiv). In this note, the author studies a variant of distribution-free property testing on graphs, in which (roughly) neighboring vertices have probabilities of bounded ratio, and a query reveals this ratio. Applications to local graph algorithms and connections to dynamical systems are also discussed.

EDIT: We apparently missed two papers from June — the first paper was accepted to NeurIPS 2019, the second to COLT 2019.**The Broad Optimality of Profile Maximum Likelihood**, by Yi Hao and Alon Orlitsky (arXiv). Recently, Acharya, Das, Orlitsky, and Suresh (ICML 2017) showed that the Profile Maximum Likelihood (PML) estimator enables a unified framework for estimating a number of distribution properties, including support size, support coverage, entropy, and distance to uniformity, obtaining estimates which are competitive with the best possible. The approach is rather clean: simply estimate the PML of the distribution (i.e., the maximum likelihood distribution of the data, if the the labels are discarded and only the multiplicities of elements are kept), and apply the plug-in estimator (i.e., if you want to estimate entropy, compute the entropy of the resulting PML distribution). The present work shows that PML is even more broadly applicable — such an approach applies to *any* property which is additive, symmetric, and appropriately Lipschitz. They also show specific results for many other properties which have been considered in the past, including Rényi entropy, distribution estimation, and identity testing.

**Sample-Optimal Low-Rank Approximation of Distance Matrices** by Piotr Indyk, Ali Vakilian, Tal Wagner, David Woodruff (arXiv). Getting a rank \(k\) approximation of an \(n \times m\) matrix \(M\) is about as classic a problem as it gets. Suppose we wanted a running time of \(O(n+m)\), which is sublinear in the matrix size. In general, this is not feasible, since there could be a single large entry that dominates the matrix norm. This paper studies the case where the matrix is itself a *distance matrix*. So there is an underlying point set in a metric space, and the \(i, j\)th entry of \(M\) is the distance between the $i$th and $j$th point. Previous work showed the existence of \(O((n+m)^{1+\gamma})\) time algorithms (for arbitrary small constant $\gamma > 0$, with polynomial dependence on \(k\) and error parameters). This work gives an algorithm that runs in \(\widetilde{O}(n+m)\) time. The main idea is to sample the rows and columns according to row/column norms.

Fast-forward to this summer: the recently concluded 3^{rd} Workshop on Local Algorithms, which took place last month at ETH Zurich, featured an open problems session. The list of open problems can be found in this link, or here for a PDF version.

Let’s start with a paper on PCPs:**Revisiting Alphabet Reduction in Dinur’s PCP**, by Venkatesan Guruswami, Jakub Opršal, and Sai Sandeep (ECCC). As mentioned in the title, this work provides an alternate proof of one of the two parts of the Dinur’s PCP theorem proof. In that proof, the argument goes by alternating two main steps: (i) amplifying the soundness gap, at the price of increasing the alphabet size (and the instance size); (ii) reducing the alphabet size, at the price of increasing the instance size. From the observation that step (i) creates some structure in the instances that can be leveraged, the authors provide an alternative construction for (ii), leading to an arguably simpler analysis of the soundness of the underlying test. A nice throwback to some of the roots of property testing.

Then, four papers on distribution testing:**Testing Mixtures of Discrete Distributions**, by Maryam Aliakbarpour, Ravi Kumar, Ronitt Rubinfeld (arXiv). One of the most studied problems in distribution testing is *identity testing* (a.k.a., goodness-of-fit): given a reference distribution \(q\) over a domain of size \(n\) and i.i.d. samples from an unknown \(p\), decide between \(p=q\) and \(d_\textrm{TV}(p,q) > \varepsilon\). While this is now well-understood and can be done with a strongly sublinear number of samples (namely, \(\sqrt{n})\)), the case of *tolerant* testing is much sadder: Valiant and Valiant proved that \(\Theta(n/\log n)\) samples were required for distinguishing \(d_\textrm{TV}(p,q) < \varepsilon/2\) from \(d_\textrm{TV}(p,q) > \varepsilon\). So, noise-tolerance is almost as hard as it gets… *except*, as this works suggests and studies, if one has some guarantees on the noise! What if the noise in the completeness case was just that \(q\) is perturbed by some (known, or available via samples as well) noise coming from a second distribution \(\eta\)? I.e., the question is now to test whether \(p\) if of the form \(\alpha q + (1-\alpha) \eta\) for some \(\alpha\in [0,1]\), or if it is \(\varepsilon\)-far from all mixtures of \(q\) and \(\eta\). The authors have various results on this question and some extensions, but the upshot is: “with structured noise, strongly sublinear sample complexity is once again possible.”**Can Distributed Uniformity Testing Be Local?**, by Uri Meir, Dor Mintzer, and Rotem Oshman (ACM PODC Proceedings). More on identity testing, specifically uniformity testing. No noise here, but another constraint: the samples are distributed. There are \(k\) players, each holding \(q\) i.i.d. samples from a distribution \(p\) over \([n]\); each can send \(\ell=1\) bit to a central referee, in a non-interactive fashion. Is \(p\) the uniform distribution, or is it \(\varepsilon\)-far from it? The authors here consider the case where \(k,n,\varepsilon\) are fixed, and prove lower bounds on the number \(q=q(k,n,\varepsilon)\) of samples each player must hold in order to perform this uniformity testing task. (Note: their lower bounds hold even in the public-randomness setting.) Motivated by the LOCAL model, they focus on 3 cases of interest, for which they obtain tight or near-tight bounds on \(q\) (in view of upper bounds from previous work of a subset of the authors): (1) when the referee’s decision has to be the \(\textsf{AND}\) of all \(n\) bits she receives; (2) when the referee can do something more involved, and use a threshold function; and (3) when the referee can use an arbitrary function of those \(n\) messages. Underlying those lower bounds is a neat application of Boolean Fourier analysis, recasting the analysis of the standard “Paninski” lower bound instance and the player’s decision functions as a question on Boolean functions.

And now… graphs!**Expansion Testing using Quantum Fast-Forwarding and Seed Sets**, by Simon Apers (arXiv). This paper is concerned with (bicriteria) testing of vertex expansion of a given graph \(G=(V,E)\) in the bounded-degree graph model. Loosely speaking, given a value \(\Phi\) and query access *(i.e., sampling a node u.a.r., querying the degree of a node, and querying the \(i\)-th neighbor of a node) *to a graph \(G\) with maximum degree \(d=\Theta(1)\), the goal is to distinguish between (i) \(G\) has vertex expansion at most \(\Phi\) and (ii) \(G\) is \(\varepsilon\)-far from any \(G’\) with vertex expansion at most \(\Phi^2\) *(simplifying and dropping some technicalities)*. The previous state-of-the-art was a \(\tilde{O}_{\varepsilon}(n^{1/2}/\Phi^2)\) query complexity for classical algorithms, and a \(\tilde{O}_{\varepsilon}(\min(n^{1/3}/\Phi^2),n^{1/2}/\Phi^2))\) query complexity upper bound for quantum testers. The current work improves on this by providing a \(\tilde{O}_{\varepsilon}(n^{1/3}/\Phi)\) quantum tester. Graphs expand—and so does the gap between classical and quantum testing.**Walking Randomly, Massively, and Efficiently**, by Jakub Łącki, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski (arXiv). One very useful primitive, in many graph property testing results and of course well beyond property testing, is the ability to perform random walks on graphs. In the case of large, distributed (or merely impractically massive) graphs, however, it is not clear how to implement this primitive efficiently. This work addresses this question in the MPC (Massive Parallel Computation) model, and shows how to perform independently, from all of the \(n\) nodes of a graph (i.e., machine), an \(\ell\)-length random walk with only \(O(\log \ell)\) rounds of communication and \(O(n^\alpha)\) space per machine, for any constant \(\alpha \in(0,1)\). This round complexity matches a known (conditional) lower bound, and thus the result is as good as it gets — further, the authors obtain such MPC algorithms for both undirected and directed graph, somehow leveraging the latter case to handle the (significantly more complicated) directed case. As an application of this efficient random walk primitive, they provide MPC property testing algorithms for both bipartiteness and vertex expansion* (same definition as in the paper above: vertex expansion \(\Phi\) vs. \(\varepsilon\)-far from any \(G’\) with vertex expansion \(\Phi^2\))* in the general graph model. (Beyond property testing, another application—the main one in the paper— is computing PageRank in both graphs and directed graphs.)**A Lower Bound on Cycle-Finding in Sparse Digraphs**, by Xi Chen, Tim Randolph, Rocco Servedio, and Timothy Sun (arXiv). In this paper, the authors tackle the problem of one-sided testing of acyclicity of directed graphs, in the bounded-degree graph model (equivalently, on the task of finding a cycle in a digraph promised to be far from acyclic). Previously, an \(\Omega(\sqrt{n})\) lower bound for this task had been shown by Bender and Ron, based on a birthday-paradox-type argument; this work improves on this hardness result, showing that \(\tilde{\Omega}(n^{5/9})\) queries are necessary. Interestingly, whether achieving any \(o(n)\) query complexity is possible remains open.

**Update:** we did miss a paper! Make it **ten** in July…**Nearly optimal edge estimation with independent set queries**, by Xi Chen, Amit Levi, Erik Waingarten (arXiv). Consider the following type of access to an unknown graph \(G=(V,E)\) on \(n=|V|\) nodes: on query \(S\subseteq V\), the oracle returns 1 if \(S\) is is an independent set, and 0 otherwise. *(This sounds quite a bit like what is allowed in the group testing literature.)* How many such queries are necessary to get a multiplicative estimate of the number of edges, \(m=|E|\)? In this paper, the authors improve on the previous bound of \(\min(\sqrt{m}, n^2/m)\) (ignoring logarithmic factors), obtaining an \(\min(\sqrt{m}, n/m)\) upper bound — complemented by a (nearly, up to those pesky log factors) matching lower bound.

*If we missed a paper this month, or represented some result above, please mention it in the comments.*

**On the Complexity of Estimating the Effective Support Size**, by Oded Goldreich (ECCC). In distribution testing, a classic problem is that of approximating the support size. By a (now) classic result of Valiant-Valiant, the complexity of this problem is \(\Theta(n/\log n)\). This paper raises the question of approximating the “effective” support, and that too with more than just samples from the distribution. The \(\epsilon\)-support of discrete distribution \(\mathcal{D}\) is the smallest support among any distribution \(\mathcal{D}’\) such that \(\|\mathcal{D} – \mathcal{D}’\|_1 \leq \epsilon\) (or TV-distance). Denote this as \(supp_\epsilon(\mathcal{D})\). One can also consider a bicriteria version. Given approximation parameter \(f\) and thresholds \(\epsilon_1 < \epsilon_2\), we need to provide a number in the range \([supp_{\epsilon_2}(\mathcal{D}), f\cdot supp_{\epsilon_1}(\mathcal{D})]\). The primary model studied allows for random samples and evaluation queries (where one gets the probability of any known element of the domain). In this model, for arbitrary \(\epsilon_1, \epsilon_2\), there is a continuum of algorithms, trading off query complexity with approximation. At one end, for \(f = O(\log n)\), the query complexity is \(\widetilde{O}(1/\epsilon_1)\). At the other end, for \(f=1\), the query complexity is \(O(\log^* n)\). (Here, \(n = supp_{\epsilon_1}(\mathcal{D})\).) There are lower bounds showing the necessity of evaluation queries for subpolynomial query complexities.

**Communication and Memory Efficient Testing of Discrete Distributions**, by Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane, and Sankeerth Rao (arXiv). This paper adds additional computational constraints to the distribution testing problem. In the streaming setting, the algorithm is only allowed a single pass over the random samples. It has \(m\) bits of storage, much smaller than \(n\), the distribution size. The aim is to minimize the number of samples required for uniformity (and closeness) testing. For uniformity testing in the streaming setting, the paper gives an algorithm that uses \(\widetilde{O}(m + n/m)\) samples. The standard collision algorithm requires \(\Theta(\sqrt{n})\) storage (to store the samples), while this result gives a non-trivial bound for \(m \ll \sqrt{n}\). There are lower bounds showing that these bounds are basically tight. In the distributed distribution testing problem, there are a number of processors, each holding \(\ell\) samples. A referee asks a question to the processor, whose answers are broadcast to everyone. The aim is to minimize communication cost. For uniformity testing in this setting, there is a protocol using \(O(\sqrt{n\log n/\ell})\) bits of communication. As a sanity check, note that for \(\ell = \sqrt{n}\), one processor could simply run the collision algorithm locally to report the result.

**Querying a Matrix through Matrix-Vector Products** by Xiaoming Sun, David P. Woodruff, Guang Yang, and Jialin Zhang (arXiv). Consider \(n \times d\) matrix \(M\) over some field \(\mathbb{F}\). One gets access to this matrix through matrix-vector products, and wishes to test some matrix property. This is a natural model in many settings, and generalizes the classic setting of query access. A subtle point is that one can only right multiply with “query” vectors, and there are problems where left multiplication can change the complexity. (A nice example in the paper is testing if a square matrix is symmetric. With both left and right multiplications, this is easy, since we can directly access rows and columns. By only accessing columns, this is non-trivial.) This paper studies a number of problems, broadly classified as linear algebra problems, statistics problems, and graph problems. Some highlights are: testing symmetry can be done in \(O(1)\) queries, and the maximum eigenvalue can be approximated in \(O(\log n)\) queries adaptively (but there is an \(\Omega(n)\) non-adaptive lower bound). For graph problems, here’s an interesting discovery. If \(M\) is the adjacency matrix, connectivity requires \(\Omega(n/\log n)\) queries. But if \(M\) is the signed edge-vertex matrix, then this can be done in \(poly(\log n)\) queries. This paper provides a number of interesting directions and problems to study.

**The Adversarial Robustness of Sampling** by Omri Ben-Eliezer and Eylon Yogev (arXiv). This isn’t a property testing paper, but how can one ignore a paper on understanding the power of sampling? It’s convenient to think of the following setting. An algorithm gets a stream of \(n\) numbers, and has to answer some questions about the stream (say, the median or other quantiles). The simplest strategy is to take a small random sample of the stream. But what if an adversary was generating the stream, depending on the current sample? Under what circumstances is the sample still “representative” of the stream? The specific results of this paper require getting into set systems and VC dimension, which I’ll leave for the sake of simplicity. Let’s go back to the median question. To get an approximate median, a constant number of samples suffice. A consequence of the main result is that if one takes \(O(\log n)\) samples, then this is robust to adversarial streams. On the other hand, lower bounds show that constant sized samples can be fooled by an adversary. The paper is a really interesting read, and is a nice take on “standard facts” that we take for granted.

EDIT: We did, in fact, miss one paper, which is the bottom one listed below.

**On Local Testability in the Non-Signaling Setting**, by Alessandro Chiesa, Peter Manohar, and Igor Shinkar (ECCC). This paper studies testability of a certain generalization of (distributions over) functions, known as \(k\)-non-signalling functions, objects which see use in hardness of approximation and delegation of computation. Prior work by the authors show the effectiveness of the linearity test in this setting, leading to the design of PCPs. On the other hand, in this work, the authors show that two types of bivariate tests are ineffective in revealing low-degree structure of these objects.

**Computing and Testing Small Vertex Connectivity in Near-Linear Time and Queries**, by Danupon Nanongkai, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai (arXiv). This work, apparently simultaneous with the one by Forster and Yang that we covered last month, also studies the problem of locally computing cuts in a graph. The authors also go further, and study approximation algorithms for the same problems. Inspired by the connections to property testing in the work of Forster and Yang, they apply these approximation algorithms to get even more query-efficient algorithms for the problems of testing \(k\)-edge- and \(k\)-vertex-connectivity.

**Testing Graphs against an Unknown Distribution**, by Lior Gishboliner and Asaf Shapira (arXiv). This paper studies graph property testing, under the vertex-distribution-free (VDF) model, as recently introduced by Goldreich. In the VDF model, rather than the ability to sample a random node, the algorithm has the ability to sample a node from some unknown distribution, and must be accurate with respect to the same distribution (reminiscent of the PAC learning model). In Goldreich’s work, it was shown that every property which is testable in the VDF model is semi-hereditary. This work strengthens this statement and proves a converse, thus providing a characterization: a property is testable in the VDF model if and only if it is both hereditary and extendable. These descriptors roughly mean that the property is closed under both removal and addition of nodes (with the choice of addition of edges in the latter case). This is a far simpler characterization than that of properties which are testable in the standard model, which is a special case of the VDF model.

**Private Identity Testing for High-Dimensional Distributions**, by Clément L. Canonne, Gautam Kamath, Audra McMillan, Jonathan Ullman, and Lydia Zakynthinou (arXiv). This work continues a recent line on distribution testing under the constraint of differential privacy. The settings of interest are multivariate distributions: namely, product distributions over the hypercube and Gaussians with identity covariance. An application of a statistic of CDKS, combined with a Lipschitz extension from the set of datasets likely to be generated by such structured distributions, gives a sample-efficient algorithm. A time-efficient version of this extension is also provided, at the cost of some loss in the sample complexity. Some tools of independent interest include reductions between Gaussian mean and product uniformity testing, balanced product identity to product uniformity testing, and an equivalence between univariate and “extreme” product identity testing.

**Testing Bipartitness in an Augmented VDF Bounded-Degree Graph Model**, by Oded Goldreich (arXiv). Another work on the vertex-distribution-free (VDF) model, as described above. In this one, Goldreich considers an augmentation of the model, where the algorithm is further allowed to query the probability of each node. With this augmentation, he gives \(\tilde O(\sqrt{n})\)-time algorithms for testing bipartiteness and cycle-free-ness, where \(n\) is the “effective support” of the distribution. That is, \(n\) is the number of nodes in the graph after discarding the nodes with minimal probability until \(\varepsilon/5\) mass is removed.

**Update (05/04): **We missed one. Seven!

**Junta correlation is testable**, by Anindya De, Elchanan Mossel, and Joe Neeman (arXiv). Junta testing really has seen a lot of attention and progress over the pass couple years! In this new work, the focus is on the *tolerant* version of (Boolean) junta testing, where the goal is to decide whether a given function \(f\colon \{-1,1\}^n\to \{-1,1\}\) is close to some \(k\)-junta, or far from any such simple function. The current paper improves on previous work of Blais, Canonne, Eden, Levi, and Ron, which showed how to distinguish between \(\varepsilon\)-close to \(k\)-junta and \(16\varepsilon\)-far from \(k\)-junta in \(O_{k,\varepsilon}(1)\) queries, in two ways: (i) the gap-factor of 16 can now be made arbitrarily small, yielding the first *fully* tolerant non-trivial junta tester; and (ii) the new algorithm also identifies the underlying “core junta” (up to permutation of the coordinates). Besides the other results contained in the paper (such as results for a relaxation of the tolerant question akin to that of Blais et al.), a key aspect of this paper is to go beyond the use of (set) influence as a proxy for distance to junta-ness which underlied all previous work, thus potentially opening a new avenue towards get fully tolerant, \(\mathrm{poly}(k,1/\varepsilon)\)-query junta testing algorithms.

**Testing Tensor Products**, by Irit Dinur and Konstantin Golubev (arXiv). In this paper, the authors consider the following testing question: given query access to a Boolean function \(f\colon [n]^d \to \mathbb{F}_2\), test whether \(f\) is of the form \(f(x) = f_1(x_1)+\dots f_d(x_d)\) (equivalently, this is the task of testing whether a \(d\)-dimensional tensor with \(\pm 1\) is of rank \(1\)). They provide two different proximity-oblivious testers (POT) for this task: a \(4\)-query one, reminiscent and building upon the BLR linearity test; as well as a \((d+1)\)-query POT *(which they dub “Shapka Test,” one can assume for their love of warm and comfortable hats)*, whose analysis is significantly simpler.

Changing direction, the next paper we saw is concerned with quantum testing of (regular, good ol’ classical) probability distributions:

**Quantum Algorithms for Classical Probability Distributions**, by Aleksandrs Belovs (arXiv). This work on quantum distribution testing considers 4 of the existing models of access to samples from an unknown probability distribution, analyzes their relationship, and argues their merits. Further, the autho establishes that for the simple hypothesis testing question of distinguishing between two (known, fixed) probability distributions \(p,q\), in all four models the optimal sample complexity is proportional to the inverse of the Hellinger distance between \(p\) and \(q\)—in contrast to the classical setting, where it is known to be proportional to the *squared* inverse of this distance.

Turning to graphs, the next work considers clustering of bounded-degree graphs, a topic we recently discussed as well:

**Robust Clustering Oracle and Local Reconstructor of Cluster Structure of Graphs**, by Pan Peng (arXiv). Consider the following noisy model: an unknown bounded-degree graph (of maximum degree \(d\)) \(G\) which is \((k, \phi_{\rm in},\phi_{\rm out})\)-clusterable (i.e., clusterable in at most \(k\) clusters of inner and outer conductances bounded by \(\phi_{\rm in},\phi_{\rm out}\)) is adversarially modified in at most \($\varepsilon d n\) edges between clusters. This noise model, introduced in this work, leads to the natural questions of “recovering the underlying graph \(G\)”: this is what the author tackles, by designing sublinear-time *local clustering oracles* and *local reconstruction algorithms* (local filters) in this setting. Further, in view of the noise model reminiscent of property testing in the bounded-degree graph setting, connections to testing clusterability are discussed; the implications of the results for testing clusterability are discussed in Section 1.4.

**A Faster Local Algorithm for Detecting Bounded-Size Cuts with Applications to Higher-Connectivity Problems**, by Sebastian Forster and Liu Yang (arXiv). The authors focus on the problem of finding an edge (or vertex) cut in a given graph from a *local* viewpoint, i.e., in the setting of local computation algorithms, and provide a slew of results in detecting bounded-size cuts. This in turn has direct implications for testing \(k\)-edge and \(k\)-vertex connectivity, directed and undirected, in both the bounded-degree and general (unbounded degree) models, improving on or subsuming the current state-of-the-art across the board *(see Section 1.2.4 of the paper, and the very helpful Tables 3 and 4, for a summary of the improvements)*.

**Random walks and forbidden minors II: A \(\mathrm{poly}(d\varepsilon^−1)\)-query tester for minor-closed properties of bounded degree graphs**, by Akash Kumar, C. Seshadhri, and Andrew Stolman (ECCC). Following their breakthrough from last May, the authors are at it again! Leveraging a random-walk approach, they resolve the following open question in testing bounded-degree graph: *is there a \(\mathrm{poly}(1/\varepsilon)\)-query tester for planarity (and, more generality, for minor-closed graph properties)? *The previous state-of-the-art, due to Levi and Ron, had a quasipolynomial dependence on \(1/\varepsilon\).

Without spoiling too much: the answer to the open question is *yes—* and further the authors settle it by showing an even more general result on testing \(H\)-freeness (for any constant-size graph \(H\)).

**Update (05/04): **

**Testing Unateness Nearly Optimally**, by Xi Chen and Erik Waingarten (arXiv). Recall that a function \(f\colon \{0,1\}^n\to \{0,1\}\) is said to be unate if there exists some \(s\in\{0,1\}^n\) such that \(f(\cdot \oplus s)\) is monotone; i.e., if \(f\) is either non-increasing or non-decreasing in each coordinate. Testing unateness has seen a surge of interest over the past year or so; this work essentially settles the question, up to polylogarithmic factors in \(n\) (and the exact dependence on \(\varepsilon\)). Namely, the authors present and analyze an \(\tilde{O}(n^{2/3}/\varepsilon^2)\)-query adaptive tester for unateness, which nearly matches the \(\tilde{\Omega}(n^{2/3})\)-query lower bound for adaptive testers previously established by Chen, Waingarten, and Xie.

\({}^\ast\) *That we saw, at least. if we missed some, please mention it in the comments below!)*

**Update:** As mentioned in the comments, we did indeed missed two (related) works on distribution estimation from a competitive viewpoint. Namely, for a large class of properties (entropy, distance to uniformity, support size…), Hao, Orlitsky, Suresh, and Wu provide in the first paper (arXiv 1904.00070) an “instance-optimal(ish)” estimator which does “as well” with \(m/\sqrt{\log m}\) samples than the natural and naive empirical estimator would do with \(m\) (thus, in some sense, *amplifying* the data size). In the following paper (arXiv 1903.01432), Hao and Orlitsky improve this and remove the “ish” to get the optimal amplification \(m/\log m\).

**Local Computation Algorithms for Spanners**, by Merav Parter, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee (arXiv). Consider the problem of computing a \(k\)-spanner for a graph \(G\). This is a subgraph \(H\), where (for any pair of vertices) the shortest path distance in \(H\) is at most \(k\) times the corresponding distance in \(G\). A Local Computation Algorithm (LCA) essentially gives sublinear query access to (some spanner) \(H\), without any preprocessing on \(G\). In other words, an LCA takes as input an edge \((i,j)\) in \(G\), and in sublinear time says “yes” or “no”. Despite no preprocessing, it is guaranteed that all the “yes” answers form a spanner, and the number of “yes” answers is small. One of the main challenges in LCAs for graph problems is getting a polynomial dependence on \(\Delta\), the maximum degree. (Many results end up with an exponential dependence on \(\Delta\), essentially assuming bounded-degree.) This paper give an LCA outputting spanners of optimal size for \(k=3,5\), with query complexity \(n^{1-\alpha}\) (for constant \(\alpha\) depending on \(k\)). The second result works for general \(k\), but has a query complexity that is \(O(\Delta^4n^{2/3})\).

**Set Cover in Sub-linear Time**, by Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee (arXiv). Set cover needs no introduction. This paper considers sublinear algorithms for set cover. It is convenient to think of the instance as a binary \(m \times n\) matrix, for \(m\) sets over a universe of size \(n\). The query model gives access to the \(j\)th non-zero entry in a desired column/row. The aim is this paper is to actually construct a set cover, and not just approximate its size (the latter problem with initiated in Nguyen-Onak). The first result shows a black-box conversion of any set cover algorithm into a sublinear query complexity algorithm. Any \(\alpha\)-approximation for set cover can be converted into an \(O(\alpha)\)-approximation, that makes \(O(m(n/k)^{\beta} + nk)\) (where \(k\) is the optimal set cover size, and \(\beta < 1\) depends on \(\alpha\)). For large \(k\), the paper gives an \(O(mn/k)\) query, \(O(\log n)\)-approximation algorithm. There are various lower bounds given, that show these dependencies are necessary.

**Distributional Property Testing in a Quantum World** by András Gilyén and Tongyang Li (arXiv). There are two aspects to quantum distribution testing. First, we can think of faster distribution testing (for classical problems) using quantum computation. Second, we can generalize the problem of distribution testing to its quantum equivalent, called density operator testing (this papers gives the first result for this quantum generalization). A distribution is a non-negative vector in \(\mathbb{R}^n\) with unit \(l_1\)-norm. The quantum generalization, a density operator, is a PSD matrix in \(\mathbb{C}^n\) with unit trace. This paper has a number of results, along both aspects. For example, for the well-known problem of testing equality of distributions under total variation distance, the papers gives an \(\widetilde{O}(\sqrt{n}/\epsilon)\) tester (an improvement over classical lower bounds). For testing equality of density operators under the same distance, the paper gives an \(O(n/\epsilon)\) tester (note that the trivial bound is \(O(n^2)\), since the operator is a matrix).