Apologies for the major delay! We have a nice bounty of 8 papers, with a big haul of graph property testing papers. Let us not delay even further and get right to it.

Sublinear-query relative-error testing of halfspaces by Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, and Tianqi Yang (arXiv). This paper studies the relative error model for property testing, which is designed for studying “sparse” inputs. Consider functions \(f, g: \mathbb{R}^n \to \{0,1\}\) over the Gaussian measure in \(\mathbb{R}^n\). Let \(p = \Pr[f(x) = 1]\), which one can think of as the “volume” of \(f\). The relative distance of \(g\) from \(f\) is defined as \(\Pr_{x}[f(x) \neq g(x)]/p\). In situations where the volume is tiny, this definition makes more sense than the standard definition, where \(f\) would simply be close to the all zero function. To get non-trivial results, one needs another oracle called SAMP that gives a random sample of a point in \(f^{-1}(1)\). This paper studies the classic problem of halfspace testing. The main results are property testers with query complexity sublinear in \(n\) and polylogarithmic in \(1/p\). Some of these testers are given the value \(p\), and some only use the SAMP oracle (so no querying of arbitrary points). In the full model of standard queries and the SAMP oracle, one can get a \(poly(\log(1/p), \varepsilon)\) query tester.

Classes Testable with \(O(1/\varepsilon)\) Queries for Small ε Independent of the Number of Variables by Nader H. Bshouty and George Haddad (arXiv). Consider property testing in the most classic setting, functions \(f:\{0,1\}^n \to \{0,1\}\). An obvious lower bound for testing any non-trivial property is \(\Omega(1/\varepsilon)\); in fewer queries, one cannot even detect the existence of an \(\varepsilon\)-fraction of the domain that may certify that input \(f\) is not in the property. When can this trivial lower bound be matched? Specifically, this paper studies parameterized properties where the tester query complexity is \(O(\psi + 1/\varepsilon)\), where \(\psi\) depends on the property parameters, and the big-Oh only hides an “absolute” constant. Take the classic problem of \(k\)-junta testing. A \(k\)-junta is a function that depends only on \(k\) variables. An old result of Blais gives a tester with query complexity \(O(k\log k + k/\varepsilon)\). But note that this does not match the trivial lower bound as \(k\) becomes large. This paper gives a tester with complexity \(O(k2^k + 1/\varepsilon)\), thereby matching the trivial lower bound even when \(k\) has some (small) dependence on \(\varepsilon\). This paper gives a number of such results for well studied properties like low Fourier degree and being a sparse polynomial.

Distributed Quantum Property Testing with Communication Constraints by Mina Doosti, Ryan Sweke, and Chirag Wadhwa (arXiv). This paper solves a quantum analogue of a distributed distribution testing problem, introduced by Acharya-Canonne-Tyagi. Suppose \(m\) machines have access to a distribution \(\rho\). An algorithm wishes to test if this distribution is close to a known distribution \(\sigma\) (the identity testing problem), and can do independent communication with each machine. This problem is studied under constraints on the amount of communication and the amount of shared randomness between the machines. The quantum equivalent of a distribution is a quantum state and communication can be either classical bits or qubits. So \(\rho, \sigma\) denotes quantum states, and the aim is property test if they are the same. This is called the quantum “certification” problem, which is the analogue of identity testing) in the distributed setting. The main results are in the setting where there is no classical communication, and the machines only send qubits.

A characterization of one-sided error testable graph properties in bounded degeneracy graphs by Oded Lachish, Amit Levi, Ilan Newman, and Felix Reidl (arXiv). For the setting of general graphs, the standard model is the Goldreich-Ron adjacency list model, as clarified by Czumaj-Sohler. Given a vertex, one can fetch a uniform random neighbor. In this model, Czumaj-Sohler completely characterized one-sided (constant query) testable properties as those described by subgraph freeness. The main result there was to show that \(H\)-freeness is constant time testable when the input graph \(G\) is minor-free. A natural super-class of minor-free graphs is that of bounded degeneracy graphs. A graph has bounded degeneracy if all subgraphs have bounded average degree; this is a rich class of graphs containing all minor-free classes, and often occurring in practice. It has been shown that testing four cycle-freeness in bounded degeneracy graphs requires \(\Omega(n^{1/4})\) queries. So it raises the natural question of characterizing the patterns \(H\) for which \(H\)-subgraph freeness is testable in constant queries. And indeed, this paper achieves exactly that, with a neat characterization.

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model by Yuichi Yoshida (arXiv). While property testing of sparse graphs has received some attention, sublinear algorithms for directed graphs is relatively unexplored. Problems become surprisingly hard, and analysis is even harder. Consider property testing of bounded outdegree graphs with no bound on indegree. The model only gives access to the out-neighborhoods, not the in-neighborhood. This asymmetry lies at the root of hardness. This paper studies the classic property of being acyclic. The main results are new lower bounds that are significant improvements over past results. Let \(n\) be the number of vertices. Ignoring log factors, One-sided testers for acyclicity require \(\Omega(n^{2/3})\) queries and two-sided testers require \(\Omega(\sqrt{n})\) queries. And tolerant testers essentially require reading the whole graph, with a lower bound of \(\Omega(n)\) queries.

Quantum Property Testing for Bounded-Degree Directed Graphs by Pan Peng and Jingyu Wu (arXiv). Same setting as above, but assume that both outdegree and indegrees are bounded. We consider the bidirectional model, which gives access to both in and out neighborhoods, as opposed to the (“standard”) unidirectional model. Pang-Wang proved that there is a property that requires \(O(1)\) queries in bidirectional model, but (almost) \(\Omega(n)\) queries in the unidirectional model. (Ignoring dependencies of \(\varepsilon\) and the degree \(d\) for clarity.) Remarkably, this paper shows that such a lower bound does not hold in the quantum model. The main result is that any property that is classically testable with \(O(1)\) queries in bidirectional model can be tested with \(o(\sqrt{n})\) queries in undirectional model with a quantum computer. Moreover, there exists a hard property with a nearly matching lower bound. One of these consequences of this result is a quantum algorithm for testing \(H\)-freeness in the unidirectional model.

Sublinear Spectral Clustering Oracle with Little Memory by Ranran Shen, Xiaoyi Zhu, Pan Peng, and Zengfeng Huang (arXiv). The focus of this paper, as the title clearly says, are sublinear spectral clustering oracles. Consider an bounded degree input graph \(G\) that is \(k\)-clusterable, which means that (say) one can remove a small fraction of edges, to get at most \(k\) connected components, each of which has high internal conductance. A line of work has shown that one can answer cluster membership queries in sublinear time, without any preprocessing of \(G\). So this is a Local Computation Algorithm (LCA) for the clusters. Any LCA has a storage budget where it keeps a data structure to ensure that all query answers are consistent with a single solution. Previous results by Peng showed that there is a clustering oracle with \(O(\sqrt{n})\) space, such that each query can be answered in \(O(\sqrt{n})\) time. One can obviously use linear space and answer queries in constant time. This paper shows a smooth tradeoff between these solutions: given \(M\) storage, there is an oracle that answers questions in \(O(n/M)\) time.

Locally Computable High Independence Hashing by Yevgeniy Dodis, Shachar Lovett, and Daniel Wichs (ECCC). Not exactly a sublinear algorithms result, but one can interpret it as an LCA result. Consider the classic problem of constructing a family \(\mathcal{F}\) of \(k\)-wise independent hash functions. Let each function be of the form \(f:\{0,1\}^n \to \{0,1\}^n\). These constructions need a seed of $O(kn)$ bits. In many settings, \(k\) is quite large, say \(poly(n)\) (so going beyond the typical constant \(k\) setting). How many queries, denoted \(t\), to the seed does it take to compute \(f(x)\), for an input \(x \in \{0,1\}^n\)? Thinking of \(n\) as small and \(k\) as large, this is exactly an LCA for the function \(f\). An old lower bound of Siegel proves that computing \(f(x)\) requires \(\Omega(t)\) queries to the seed. The main result of this paper is giving a construction that matches this bound; unfortunately, the construction is non-constructive and depends on the existence of certain expanders. If we relax the independence condition to “almost” independent (up to some precision parameter \(\varepsilon\)), then the paper gives an explicit construction.