I hope all of you are keeping safe and healthy in these difficult times. Thank heavens we have our research and our math to keep our sanity…

This month has seen two papers, one on testing variable partitions and one on distributed isomorphism testing.

Learning and Testing Variable Partitions by Andrej Bogdanov and Baoxiang Wang (arXiv). Consider a function \(f:\Sigma^n \to G\), where \(G\) is Abelian group. Let \(V\) denote the set of variables. The function \(f\) is \(k\)-separable if there is a partition \(V_1, V_2, \ldots, V_k\) of \(V\) such that \(f(V)\) can be expressed as the sum \(f_1(V_1) + f_2(V_2) + \ldots + f_k(V_k)\). This is an obviously natural property to study, though the specific application mentioned in the paper is high-dimensional reinforcement learning control. There are a number of learning results, but we’ll focus on the main testing result. The property of \(k\)-separability can be tested with \(O(kn^3/\varepsilon)\) queries, for \(\Sigma = \mathbb{Z}_q\) (and distance between functions is the usual Hamming distance). There is an analogous result (with different query complexity) for \(\Sigma = \mathbb{R}\). It is also shown that testing 2-separability requires \(\Omega(n)\) queries, even with 2-sided error. The paper, to its credit, also has empirical studies of the learning algorithm with applications to reinforcement learning.

Distributed Testing of Graph Isomorphism in the CONGEST model by Reut Levi and Moti Medina (arXiv). This result follows a recent line of research in distributed property testing algorithms. The main aim is to minimize the number of rounds of (synchronous) communication for a property testing problem. Let \(G_U\) denote the graph representing the distributive network. The aim is to test whether an input graph \(G_K\) is isomorphic to \(G_U\). The main property testing results are as follows. For the dense graph case, isomorphism can be property tested (with two-sided error) in \(O(D + (\varepsilon^{-1}\log n)^2) \) rounds, where \(D\) is the diameter of the graph and \(n\) is the number of nodes. (And, as a reader of this blog, you probably know what \(\varepsilon\) is already…). There is a standard \(\Omega(D)\) lower bound for distributed testing problems. For various classes of sparse graphs (like bounded-degree minor-free classes), constant time isomorphism (standard) property testers are known. This paper provides a simulation argument showing that standard/centralized \(q\)-query property testers can be implemented in the distributed model, in \(O(Dq)\) rounds (this holds for any property, not just isomorphism). Thus, these simulations imply \(O(D)\)-round property testers for isomorphism for bounded-degree minor-free classes.

Happy new year! And now for the last post of 2019 papers. We have found a diverse collection of six papers, ranging from classic property testing topics to new perspectives on sublinear computation.

Sublinear Optimal Policy Value Estimation in Contextual Bandits by Weihao Kong, Gregory Valiant, Emma Brunskill (arXiv). This isn’t our usual sublinear paper, but it is definitely of interest to us sublinear folk. Let’s start with a stripped down definition of the problem (or rather, game). There are \(K\) “arms”, where the \(i\)th arm is represented by an unknown vector in \(\beta_i \in \mathbb{R}^d\). We are presented with a “context”, which is a vector \(x \in \mathbb{R}^d\). Our job is to choose an arm \(i \in [K]\). We get the reward \(x \cdot \beta_i\) (with some noise added). The contexts appears from a known distribution. To aid us, we observe the rewards of \(N\) iid contexts, so we observe a total of \(T = KN\) rewards. There has been much work on figuring out the minimum value of \(T\) required to learn the optimal policy. One requires at least \(d\) (the dimension) samples to estimate any of the arm vectors. This papers shows that one can actually estimate the expected reward of the optimal policy, without being able to describe it, with sublinear in \(d\) (technically, \(\widetilde{O}(\sqrt{d})\)) samples. We see this a lot in property testing, where producing the “optimal” solution for a problem requires linear-in-dimension samples, but estimating the optimal value is much cheaper (consider, for example, the situation of linearity testing, where we wish to find the closest linear function).

Sublinear Time Numerical Linear Algebra for Structured Matrices by Xiaofei Shi and David P. Woodruff (arXiv). This follows the recent linear of advances in sublinear time linear algebra. Given a matrix \(A \in \mathbb{R}^{n \times d}\), the aim is to get algorithms that only look at \(o(nnz(A))\) entries (where \(nnz(A)\) is the number of non-zeroes, or the support). Consider the classic talk of low rank approximation. Unfortunately, suppose one entry is extremely large, and the others are extremely small. One has to find this large entry for any reasonable approximation, which (in the worst-case) requires \(nnz(A)\) queries into \(A\). Thus, previous papers make structural assumption (such as, \(A\) being a Vandermonde matrix) to get sublinear bounds. This paper gives a clean black box method to get a variety of such results. Basically, one can replace the usual \(nnz(A)\) term in many algorithms, by \(T(A)\), which is the time to compute the matrix-vector product \( Ay\), for \(y \in \mathbb{R}^d\). In many cases \(T(A) = \widetilde{O}(n)\), which can be significantly smaller than \(nnz(A)\). This paper gives such results for low-rank approximations and many regression problems.

Robust and Sample Optimal Algorithms for PSD Low-Rank Approximation by Ainesh Bakshi, Nadiia Chepurko, and David P. Woodruff. Consider the low rank problem discussed above. As mentioned in the previous paragraph, we need structural assumptions on \(A\). Previous results gave sublinear time low-rank approximations assuming that \(A\) is positive semidefinite (PSD). The aim is to get a rank \(k\) matrix \(B\) such that \(\|A-B\|^2_2\) is at most \((1+\epsilon)\)-times the optimal such approximation. The previous algorithm of Musco-Woodruff makes \(\widetilde{O}(nk/\epsilon^{2.5})\) queries in to \(A\), while there is a lower bound of \(\Omega(nk/\epsilon)\). This gap between the complexities is resolved in this paper with an upper bound of \(\widetilde{O}(nk/\epsilon)\) queries.

Constructive derandomization of query algorithms by Guy Blanc, Jane Lange, and Li-Yang Tan (arXiv). This paper discusses an intriguing angle to sublinear question: when can they be derandomized? Abstractly, consider a randomized algorithm \(R\) that makes \(q\) queries. Think of \(R\) as a function \(R(x,r)\), where \(x\) is the input, and \(r\) is the randomness. We would like to design a deterministic algorithm \(D\) making, ideally, close to \(q\) queries and approximates \(\mathop{E}_r[R(x,r)]\). For starters, consider some distribution over \(x\), and suppose we want \(\mathbb{E}_x[D(x) – \mathbb{E}_r[R(x,r)]] < \epsilon\). By (the easy direction of) Yao’s minimax lemma, one can show the existence of such an algorithm \(D\) that makes \(O(q/\epsilon)\) queries. But how to explicitly construct it? Indeed, the first result of this paper gives a “meta-algorithm” that takes as input the description of \(R\) (which is of size \(N\)), has running time \(poly(N)2^{O(q/\epsilon)}\) and outputs a description of \(D\). When \(R\) satisfies the stronger property of “bounded error”, one can get a \(O(q^3)\)-query algorithm \(D\) that approximates \(\mathop{E}_r[R(x,r)]\) for all \(x\) (again, the existence is proven by a classic theorem of Nisan). Overall, this paper gives a method to derandomize sublinear time algorithms, and I wonder if there could be some applications of this method for proving lower bounds. After all, Yao’s minimax theorem is the tool for property testing lower bounds, and any perspective on Yao’s theorem is likely of relevance.

Testing Membership for Timed Automata by Richard Lassaigne and Michel de Rougemont (arXiv). Property testing for regular languages is a classic result in sublinear algorithms. This paper focuses on the more complex notion of timed automata. The technical definition is quite complicated, but here’s an overview. There is a finite automaton and a collection of “clocks”. Imagine a string being processed, where each alphabet symbol appears with a new timestamp. Thus, the input word is called a “timed word”. The transitions of the automaton involve the new symbol read, as well as constraints involving the clock times and the timestamp. Thus, we can enforce conditions like “only transition if another symbol is read within a single time unit”. In general, deciding whether a timed word is accepted by a timed automaton is NP-complete. This papers studies the property testing viewpoint. The paper gives a new definition of “timed edit distance” between timed words. The main result shows that one can distinguish time words accepted by a timed automaton from words that are far (according to timed edit distance), by querying a constant number of word positions.

On the query complexity of estimating the distance to hereditary graph properties by Carlos Hoppen, Yoshiharu Kohayakawa, Richard Lang, Hanno Lefmann, and Henrique Stagni (arXiv). This paper concerns the classic setting of property testing of dense graphs. It is well-known that all hereditary graph properties are testable, and are moreover, one can estimate the distance to the property in time that only depends on \(\varepsilon\). Unfortunately, the queries complexities have large tower dependencies on \(\varepsilon\), arising from the use of the Szemeredi regularity lemma. The question of property testing in dense graphs can be reduced to finding “removal” lemmas (such as the classic triangle remove lemma). Such a lemma states that if at least \(\varepsilon n^2\) edges need to be removed from \(G\) to destroy all “forbidden subgraphs”, then there must be “many” forbidden subgraphs in \(G\). There is much recent research on finding families of forbidden subgraphs, where the “many” (in the above statement) is at least \(poly(\varepsilon)\) times the trivial upper bound. This paper shows that one can also estimate the distance to any hereditary property, in a query complexity that depends directly on the corresponding removal lemma parameters. As a compelling example, one can estimate the distance to being chordal in \(\exp(1/\varepsilon)\) queries, a significant improvement over standard tower bounds.

Five Six papers this month: results on testing separations, linearity testing in \(\mathbb{R}^n\), testing for regular languages, graph property testing, topological property testing, and Boolean rank.

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.

We’ve got four papers this month. A mix of distribution testing, matrix problems, and a different paper on the power of sampling.

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.

A lean month by our (now high) standards. Three papers, on local computational algorithms for spanners, sublinear set cover, and quantum distribution testing.

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).

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).

Three Four papers for July. New sublinear graph algorithms, distribution testing under new models, and sublinear matrix algorithms. Onward ho…
(Sorry Amit, for missing your paper on sublinear matrix algorithms.)

Metric Sublinear Algorithms via Linear Sampling, by Hossein Esfandiari and Michael Mitzenmacher (arXiv). Consider a weighted clique \(G = (V,E)\) where \(V\) is a set of points in a metric space and edge weights are metric distances. In this setting, sublinear algorithms are those that make \(o(n^2)\) edge queries. This paper studies problems like densest subgraph and maxcut in this setting. The key method is a sparsifying algorithm that achieves the following. (I paraphrase their language.) Consider a positive parameter \(\alpha\), and let \(w(e)\) denote the weight of edge \(e\). The aim is to get a subgraph \(H\) that contains every edge \(e\) (in \(G\)) with independent probability \(\min(w(e)/\alpha, 1)\). Furthermore, this subgraph should be obtained in time linear in the number of edges in \(H\) (hence the title of the paper). For problems like 1/2-approximating the densest subgraph and PTASes for maxcut, the results show that for a carefully chosen \(\alpha\), approximate solutions on \(H\) give solutions of comparable quality on \(G\). These results cleanly generalize to settings where edge weights satisfy triangle inequality with some multiplicative penalty.

Sublinear Algorithms for (\(\Delta\) + 1) Vertex Coloring, by Sepehr Assadi, Yu Chen, and Sanjeev Khanna (arXiv). Arguably, the first thing you learn about vertex coloring is that a graph with maximum degree \(\Delta\) admits a \((\Delta+1)\)-coloring, that can be found in linear time. But what about sublinear time/space? I like this! You take a simple classical fact, throw in sublinear constraints, and it opens up a rich theory. This paper shows a non-adaptive \(O(n^{3/2})\)-time algorithm for this problem, and gives a nearly matching lower bound. There are also results for streaming and parallel computation, but let’s focus on the sublinear result. It is remarkable that there is no loss in colors in going to sublinear time. (In contrast, the papers shows an \(\Omega(n^2)\) lower bound for constructing a maximal matching.) The main technical tool is a list coloring result, where each vertex is given a list of colors and much choose its own from that list. Obviously, if each list is \([\Delta + 1]\), such a coloring is possible. The paper proves that even if each list is an independent \(O(\log n)\)-sized sample of \([\Delta+1]\), a valid coloring is still possible. The final algorithm is pretty involved, and uses this meta-algorithm as a building block.

Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing, by Gautam Kamath and Christos Tzamos (ECCC). The standard model for distribution testing is access to samples from the unknown distribution \(\mathcal{D}\) with support \([n]\). This has attracted much attention with a rich set of results, and the complexity classic problems of uniformity, identity, and equivalence are well understood. But there are alternate models, such as the model of conditional samples (Chakraborty-Fischer-Goldhirsh-Matsliah ’13 and Canonne-Ron-Servedio ’14). For any subset \(S \subseteq [n]\), we can get a random sample from \(\mathcal{D}\) restricted to \(S\). This adds an algorithmic dimension to distribution testing. This paper studies the power of non-adaptive conditional (NACOND) queries. The main result is that uniformity, identity, and equivalence are testable with \(\mathrm{poly}(\log n)\) queries. (There are existing \(\Omega(\log n)\) lower bounds for all these problems.) The heart of these algorithms is a procedure ANACONDA that tries to find a set \(S\) where some element has a high probability, relative to the mass of \(S\).

Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices, by Amit Levi and Yuichi Yoshida (arXiv). When it comes to fundamental problems, it’s hard to beat quadratic minimization. Given a matrix \(A \in \mathbb{R}^{n\times n}\), we wish to find \(v \in \mathbb{R}^n\) that minimizes \(v^TAv\). (This is basically a singular value/vector problem.) One may have additional terms in the objective, depending on \(v^Tv\) or \(v^Tb\) (for fixed vector \(b\)). This paper gives sublinear algorithms for this problem. A natural approach is to simply subsample \(k\) rows and columns to get submatrix \(B\), solve the problem for \(B\), and hope for the best. This idea has a rich history from seminal work of Frieze-Kannan. Recently, Hayashi-Yoshida show that constant \(k\) (only depending on error parameters) suffice for getting a non-trivial approximation for this problem. Unfortunately, the solution error depends on the \(\ell_\infty\)-norm of the solution. This paper shows that for polylogarithmic \(k\), one can get an error depending on the \(\ell_2\)-norm of the solution. This is a significant improvement, especially for sparse solution vectors. The main technical workhorse is a new matrix decomposition theorem, that shows how any matrix can be written as a sum of a few block matrix, and a low-norm “error” matrix. Admirably, the paper shows a number of experiments,
showing the effectiveness of this technique for eigenvalue computations. It’s very nice to see how ideas from sublinear algorithms might have a practical impact.

Three Four papers for April: a new take on linearity testing, results on sublinear algorithms with advice, histogram testing, and distributed inference problems. (Edit: Sorry Clément, for missing your paper on distributed inference!)

Testing Linearity against Non-Signaling Strategies, by Alessandro Chiesa, Peter Manohar, and Igor Shinkar (ECCC). This paper gives a new model for property testing, through the notion of non-signaling strategies. The exact definitions are quite subtle, but here’s a condensed view. For \(S \subseteq \{0,1\}^n\), let an \(S\)-partial function be one that is only defined on \(S\). Fix a “consistency” parameter \(k\). Think of the “input” as a collection of distributions, \(\{\mathcal{F}_S\}\), where each \(|S| \leq k\) and \(\mathcal{F}_S\) is a distribution of \(S\)-partial functions. We have a local consistency requirement: \(\{\mathcal{F}_S\}\) and \(\{\mathcal{F}_T\}\) must agree (as distributions) on restrictions to \(S \cap T\). In some sense, if we only view pairs of these distributions of partial functions, it appears as if they come from a single distributions of total functions. Let us focus on the classic linearity tester of Blum-Luby-Rubinfeld in this setting. We pick random \(x, y, x+y \in \{0,1\}^n\) as before, and query these values on a function \(f \sim {\mathcal{F}_{x,y,x+y}}\). The main question addressed is what one can say about \(\{\mathcal{F}_S\}\), if this linearity test passes with high probability. Intuitively (but technically incorrect), the main result is that \(\{\mathcal{F}_S\}\) is approximated by a “quasi-distribution” of linear functions.

An Exponential Separation Between MA and AM Proofs of Proximity, by Tom Gur, Yang P. Liu, and Ron D. Rothblum (ECCC). This result follows a line of work on understanding sublinear algorithms in proof systems. Think of the standard property testing setting. There is a property \(\mathcal{P}\) of \(n\)-bit strings, an input \(x \in \{0,1\}^n\), and a proximity parameter \(\epsilon > 0\). We add a proof \(\Pi\) that the tester (or the verifier) is allowed to use, and we define soundness and completeness in the usual sense of Arthur-Merlin protocols. For a \(\mathbb{MA}\)-proof of proximity, the proof \(\Pi\) can only depend on the string \(x\). In a \(\mathbb{AM}\)-proof of proximity, the proof can additionally depend on the random coins of the tester (which determine the indices of \(x\) queried). Classic complexity results can be used to show that the latter subsume the former, and this paper gives a strong separation. Namely, there is a property \(\mathcal{P}\) where any \(\mathbb{MA}\)-proof of proximity protocol (or tester) requires \(\Omega(n^{1/4})\)-queries of the input \(x\), but there exists an \(\mathbb{AM}\)-proof of proximity protocol making \(O(\log n)\) queries. Moreover, this property is quite natural; it is simply the encoding of permutations.

Testing Identity of Multidimensional Histograms, by Ilias Diakonikolas, Daniel M. Kane, and John Peebles (arXiv). A distribution over \([0,1]^d\) is a \(k\)-histogram if the domain can be partitioned into \(k\) axis-aligned cuboids where the probability density function is constant. Recent results show that such histograms can be learned in \(k \log^{O(d)}k\) samples (ignoring dependencies on accuracy/error parameters). Can we do any better for identity testing? This paper gives an affirmative answer. Given a known \(k\)-histogram \(p\), one can test (in \(\ell_1\)-distance) whether an unknown \(k\)-histogram \(q\) is equal to \(p\) in (essentially) \(\sqrt{k} \log^{O(d)}(dk)\) samples. There is a nearly matching lower bound, when \(k = \exp(d)\).

Distributed Simulation and Distributed Inference, by Jayadev Acharya, Clément L. Canonne, and Himanshu Tyagi (arXiv   ECCC). This papers introduces a model of distributed simulation, which generalizes distribution testing and distributed density estimation. Consider some unknown distribution \(\mathcal{D}\) with support \([k]\), and a “referee” who wishes to generate a single sample from \(\mathcal{D}\) (alternately, she may wish to determine if \(\mathcal{D}\) has some desired property). The referee can communicate with “players”, each of whom can generate a single independent sample from \(\mathcal{D}\). The catch is that each player can communicate at most \(\ell\) < \(log_2k\) bits (otherwise, the player can simply communicate the sampled element). How many players are needed for the referee to generate a single sample? The paper first proves that this task is basically impossible with a (worst-case) finite number of players, but can be done with expected \(O(k/2^\ell)\) players (and this is optimal). This can plugged into standard distribution testing results, to get inference results in this distributed, low-communication setting. For example, the paper shows that identity testing can be done with \(O(k^{3/2}/2^\ell)\) players.

And now, for the first papers of 2018! It’s a slow start with only four papers (or technical three “standard property testing” papers, and one non-standard paper).

Adaptive Boolean Monotonicity Testing in Total Influence Time, by Deeparnab Chakrabarty and C. Seshadhri (arXiv ECCC). The problem of testing monotonicity of Boolean functions \(f:\{0,1\}^n \to \{0,1\}\) has seen a lot of progress recently. After the breakthrough results of Khot-Minzer-Safra giving a \(\widetilde{O}(\sqrt{n})\) non-adaptive tester, Blais-Belovs proved the first polynomial lower bound for adaptive testers, recently improved to \(O(n^{1/3})\) by Chen, Waingarten, and Xi. The burning question: does adaptivity help? This result shows gives an adaptive tester that runs in \(O(\mathbf{I}(f))\), the total influence of \(f\). Thus, we can beat these lower bounds (and the non-adaptive complexity) for low influence functions.

Adaptive Lower Bound for Testing Monotonicity on the Line, by Aleksandrs Belovs (arXiv). More monotonicity testing! But this time on functions \(f:[n] \to [r]\). Classic results on property testing show that monotonicity can be tested in \(O(\varepsilon^{-1}\log n)\) time. A recent extension of these ideas by Pallavoor-Raskhodnikova-Varma replace the \(\log n\) with \(\log r\), an improvement for small ranges. This paper proves an almost matching lower bound of \((\log r)/(\log\log r)\). The main construction can be used to give a substantially simpler proof of an \(\Omega(d\log n)\) lower bound for monotonicity testing on hypergrids \(f:[n]^d \to \mathbb{N}\). The primary contribution is giving explicit lower bound constructions and avoiding Ramsey-theoretical arguments previously used for monotonicity lower bounds.

Earthmover Resilience and Testing in Ordered Structures, by Omri Ben-Eliezer and Eldar Fischer (arXiv). While there has been much progress on understanding the constant-time testability of graphs, the picture is not so clear for ordered structures (such as strings/matrices). There are a number of roadblocks (unlike the graph setting): there are no canonical testers for, say, string properties, there are testable properties that are not tolerant testable, and Szemeredi-type regular partitions may not exist for such properties. The main contribution of this paper is to find a natural, useful condition on ordered properties such that the above roadblocks disappear hold, and thus we have strong testability results. The paper introduces the notion of Earthmover Resilient properties (ER). Basically, a graph properties is a property of symmetric matrices that is invariant under permutation of base elements (rows/columns). An ER property is one that is invariant under mild perturbations of the base elements. The natural special cases of ER properties are those over strings and matrices, and it is includes all graph properties as well as image properties studied in this context. There are a number of characterization results. Most interestingly, for ER properties of images (binary matrices) and edge-colored ordered graphs, the following are equivalent: existence of canonical testers, tolerant testability, and regular reducibility.

Nondeterminisic Sublinear Time Has Measure 0 in P, by John Hitchcock and Adewale Sekoni (arXiv). Not your usual property testing paper, but on sublinear (non-deterministic) time nonetheless. Consider the complexity class of \(NTIME(n^\delta)\), for \(\delta < 1\). This paper shows that this complexity class is a "negligible" fraction of \(P\). (The analogous result was known for \(\alpha < 1/11\) by Cai-Sivakumar-Strauss.) This requires a technical concept of measure for languages and complexity classes. While I don’t claim to understand the details, the math boils down to understanding the following process. Consider some language \(\mathcal{L}\) and a martingale betting process that repeatedly tries to guess the membership of strings \(x_1, x_2, \ldots\) in a well-defined order. If one can define such a betting process with a limited computational resource that has unbounded gains, then \(\mathcal{L}\) has measure 0 with respect to that (limited) resource.

After the flood of papers over the past few months, it’s reduced to “merely” six papers this October. And only two papers on distribution testing 🙂 (Update: Gautam pointed out another paper that also does distribution testing under Wasserstein distance.)

Proofs of Proximity for Distribution Testing, by Alessandro Cheisa and Tom Gur (ECCC). Take 1 on distribution testing. As usual, we have a distribution \(\mathcal{D}\) over \([n]\), a property \(\mathbf{P}\) of distributions, and a proximity parameter \(\varepsilon > 0\). But our tester is now aided by a purported proof (or a prover). If \(\mathcal{D} \in \mathbf{P}\), there must exist a proof/prover strategy that makes the tester accept. If \(\mathcal{D}\) is \(\varepsilon\)-far from \(\mathbf{P}\), for any proof/prover strategy, the tester must reject with high probability. This paper studies a number of settings: deterministic vs randomized testers, proof (a la \(\mathbb{NP}\) or \(\mathbb{MA}\)) vs provers (a la \(\mathbb{IP}\)). There are a number of very intriguing results, so here are some highlights. For every property, there is a near-linear proof that allows for \(O(\sqrt{n})\) testers. For every property, either the proof length or the tester (sample) complexity is at least \(\Omega(\sqrt{s})\), where \(s\) is the optimal complexity of a vanilla tester. But there exist prover strategies that can beat this lower bound.

Wasserstein Identity Testing, by Shichuan Deng, Wenzheng Li, and Xuan Wu (arXiv). For Take 2 on distribution testing, this paper considers the problem on continuous distributions. In all results on distribution testing, the sample complexity depends on the support size. This breaks down in this setting, so this paper focuses on identity testing according to Wasserstein distance (as opposed to \(\ell_p\)-norms). A previous paper of Do Ba-Nguyen-Nguyen-Rubinfeld also considers the same problem, where the domain is assumed to be \([\Delta]^d\). In this paper, we assume that the domain \(X\) is endowed with a metric space, to allow for the definition of Wasserstein/earthmover distance between distributions. The final result is technical, depends on the size of nets in \(X\), and is shown to be optimal for testing equality with a known distribution \(p\). The paper also gives an instance optimal for (almost) all \(p\), a la Valiant-Valiant for the discrete case.

Improved Bounds for Testing Forbidden Order Patterns, by Omri Ben-Elizer and Clément Canonne (arXiv). Any function from \(f:D \to \mathbb{R}\), where \(D\) is a total order, can be thought to induce a permutation, based on the order of function values. Consider \(f:[n] \to \mathbb{R}\) and permutation \(\pi \in S_k\). The property of \(\pi\)-free permutations is the set of \(f\) such that no restriction of \(f\) (to a subdomain of size \(k\)) induces \(\pi\). Newman et al proved that this property can be tested non-adaptively in (ignoring \(\varepsilon\)) \(O(n^{1-1/k})\) samples. Furthermore, for non-monotone \(\pi\), there is a non-adaptive \(\Omega(\sqrt{n})\) lower bound. This paper has a number of results that shed significant light on the non-adaptive complexity. The upper bound is improved to \(O(n^{1-1/(k-1)})\), and there exist a class of permutations (for every \(k\)) for which this is the optimal complexity. Furthermore, for a random \(\pi\), the paper shows a lower bound of \(\Omega(n^{1-1/(k-3)})\). There is an intriguing conjecture on the optimal complexity for any \(k\), that has an intricate dependence on the structure of \(k\). On the adaptive side, there is an interesting hierarchy for testing \((1,3,2)\)-freeness, depending on the number of rounds of adaptivity. There is an \(O(n^{1/(r+1)})\) tester with \(r\)-rounds of adaptivity, and any such tester requires \(O(n^{1/2^{r+3}})\) queries.

A \(o(d)\cdot \mathrm{poly}\log n\) Monotonicity Tester for Boolean Functions
over the Hypergrid \([n]^d\), by Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri (arXiv). Monotonicity testing has seen much progress in the past few years. This paper focuses on monotonicity testing over the hypergrid, of functions \(f:[n]^d \to \{0,1\}\). For \(n=2\) (the hypercube), the result of Khot-Minzer-Safra gives a \(\widetilde{\sqrt{d}}\) time (non-adaptive) tester. Previously, the best known tester for general \(n\) took \(O(d\log d)\) queries, by Berman-Raskhodnikova-Yaroslavtsev. This paper breaks the barrier of \(d\) queries for the hypergrid, by giving a \(O(d^{5/6}\log n)\) time tester. The main technical ingredient is a new isoperimetric inequality for the directed “augmented” hypergrid, where pairs differing on one coordinate by a power of 2 are also connected. The intriguing open question that remains is the existence of testers with query complexity sublinear in \(d\) and independent of \(n\).

Provable and practical approximations for the degree distribution using sublinear graph samples, by Talya Eden, Shweta Jain, Ali Pinar, Dana Ron, and C. Seshadhri (arXiv). The degree distribution of a simple, undirected graph \(G\) is the sequence \(\{n_d\}\), where \(n_d\) is the number of vertices of degree \(d\). The properties of the degree distribution have played a significant role in network science and the mathematical study of real-world graphs. It is often the first quantity computed in a “data analysis” of a massive graph. This paper addresses the problem of getting (bicriteria) estimates for all values of the degree distribution, in sublinear time. The main result gives sublinear time algorithms for computing degree distributions with sufficiently “fat” tails, as measured by certain fatness indices. For the important special case, when the degree distribution is a power law (\(n_d \propto 1/d^{\gamma}\)), this result yields strictly sublinear algorithms. Interestingly, the main result involves the h-index of the degree sequence, inspired by bibliographic metrics. This problem is practically important, and the paper demonstrates the quality of the sublinear algorithm in practice.

On the Complexity of Sampling Vertices Uniformly from a Graph, by Flavio Chierichetti and Shahrzad Haddadan (arXiv). This paper isn’t your traditional property testing paper, but is very relevant to those of us interested in graph property testing. One common query model in graph property testing is access to uniform random vertices. In practice though (think of a graph like the Facebook friendship network or the web graph), this is quite challenging. We typically have access to a few seed vertices, and we can “crawl” the graph. A natural approach is to perform a random walk (in the hope of mixing quickly) to generate random vertices. We might attempt rejection sampling or Metropolis-Hastings on top of that to get uniform random vertices. A recent result of Chierichetti et al give an algorithm for this problem using \(O(t_{mix} d_{avg})\) samples, where \(t_{mix}\) is the mixing time (of the random walk on the graph) and \(d_{avg}\) is the average degree. This paper proves that this bound is optimal, for most reasonable choices of these parameters.