News for April 2018

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.

News for January 2018

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.

News for October 2017

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.

News for July 2017

We’re seeing lots of papers in the summer. I guess the heat and sun (and more time?) is bringing out the good stuff. Distribution testing, from testing to streaming, hypergraph testing, and bunch of papers on graph testing. And just for the record: in what follows, $$n$$ is the support size in distribution testing, it’s the number of vertices in graph testing, and it’s the length when the input is a string. And $$m$$ is the number of edges when the input is a graph. Amen. (Update: added a paper on testing Dyck languages. 11 papers this month, I think that’s a PTReview record.)

Which Distribution Distances are Sublinearly Testable?, by Constantinos Daskalakis, Gautam Kamath, and John Wright (Arxiv). Distribution testing is seeing much progress these days. Many questions in this area can be formulated as: given a known distribution $$q$$, how many samples from an unknown distribution $$p$$ are required to determine the distance between $$p$$ and $$q$$? For the “identity testing” setting, we are given discrete distribution $$q$$, two distance measures $$d_1, d_2$$, and proximity parameters $$\varepsilon_1, \varepsilon_2$$. How many samples from unknown distribution $$p$$ are required to distinguish $$d_1(p,q) \leq \varepsilon_1$$ from $$d_2(p,q) \geq \varepsilon_2$$? Observe the asymmetric nature of the question. The choices for the distributions are most of the standard ones: TV, KL-divergence, Hellinger, $$\chi^2$$, and $$\ell_2$$. And the paper basically completes the entire picture by giving matching upper and lower bounds (in terms of the support size $$n$$) and showing certain settings that are untestable with sublinear sample complexity. The results also consider the “equivalence/closeness testing” case, where $$q$$ is also unknown. There are many interesting aspects of this collection of results. For example, when $$d_1$$ is KL-divergence instead of $$\chi^2$$, the complexity can jump from $$\Theta(\sqrt{n})$$ to $$\Theta(n/\log n)$$.

We have two independent papers with similar results (and titles!).

Differentially Private Identity and Closeness Testing of Discrete Distributions, by Maryam Aliakbarpour, Ilias Diakonikolas, and Ronitt Rubinfeld (arXiv). Differentially Private Testing of Identity and Closeness of Discrete Distributions, by Jayadev Acharya, Ziteng Sun, and Huanyu Zhang (arXiv). Both these papers study the problem of identity testing over TV-distance, in the differentially private setting. In essence, the distribution testing algorithm should not be able to distinguish between two “neighboring” input distributions $$p, p’$$. The main result, achieved in both papers, is such an algorithm for identity (and closeness) testing whose sample complexity is quite close to the best non-differentially private algorithms. At a high level, the approaches used are also similar, specifically using a result of Goldreich on black-box reductions from identity to uniformity testing, and designing a private version of Paninski’s uniformity tester.

Estimating parameters associated with monotone properties, by Carlos Hoppen, Yoshiharu Kohayakawa, Richard Lang, Hanno Lefmann, and Henrique Stagni (arXiv). The study of monotone graph properties has rich history in graph property testing. This paper focuses on constant-query estimation of monotone graph parameters. A monotone graph property is one that is closed under subgraphs, and a monotone parameter is one that is non-increasing for subgraphs. Given a family of (constant-size) graphs $$\mathcal{F}$$, a graph is $$\mathcal{F}$$-free if it contains no subgraph in $$\mathcal{F}$$. For any graph $$G$$, define the parameter $$z_\mathcal{F}$$ to be (essentially) the log of the number of $$\mathcal{F}$$-free spanning subgraphs of $$G$$. This parameter has been studied in the context of subgraph counting problems. This papers studies the complexity of estimating $$z_\mathcal{F}$$ up to additive error $$\varepsilon$$. Most results of this flavor typically involve complexities that are towers in $$1/\varepsilon$$, but this result builds connections with the breakthrough subgraph removal lemma of Fox, to yield complexities that are towers in $$\log(1/\varepsilon)$$.

Testable Bounded Degree Graph Properties Are Random Order Streamable, by Morteza Monemizadeh, S. Muthukrishnan, Pan Peng, and Christian Sohler (arXiv). This paper proves a nice connection between sublinear and streaming algorithms. A number of properties, such as connectivity, subgraph-freeness, minor-closed properties, are constant-time testable in the bounded-degree graph setting. The main result here shows that any such property can also be tested using constant space (in terms of words) when the graph is a random order stream. In contrast, existing work by Huang and Peng proves $$\Omega(n)$$ space lower bounds for some of these properties for adversarial edge order. The main technical ingredient is an algorithm that maintains distributions of constant-sized rooted subgraphs in the random-order streaming setting.

On Testing Minor-Freeness in Bounded Degree Graphs With One-Sided Error, by Hendrik Fichtenberger, Reut Levi, Yadu Vasudev, and Maximilian Wötzel (arXiv). A major open problem in testing of bounded-degree graphs is the one-sided testability of minor-closed properties. Benjamini, Schramm, and Shapira first proved that minor-closed properties are two-sided testable, and conjectured that the one-sided complexity is $$O(\sqrt{n})$$. Czumaj et al prove this result for the specific property of being $$C_k$$-minor free (where $$C_k$$ is the $$k$$-cycle). This paper gives a $$O(n^{2/3})$$ algorithm for testing whether a graph is $$k \times 2$$-grid minor-free. The latter class includes graphs that are cycles with non-intersecting chords and cactus graphs. A common approach in one-sided graph testing is to use the existence of a “nice” decomposition
of the graph into small well-behaved pieces, and argue that the tester only has to look within these pieces. This result employs a recent partitioning scheme of Lenzen and Levi into pieces of size $$O(n^{1/3})$$. Unfortunately, this partitioning may remove many edges, and the tester is forced to find minors among these cut edges. The combinatorics of the $$k \times 2$$-grid minor ensures that any such large cut always contains such a minor, and it can be detected efficiently.

Testing bounded arboricity, by Talya Eden, Reut Levi, and Dana Ron (arXiv). The arboricity of a graph is the minimum number of spanning forests that a graph can be decomposed into. It is a 2-approximation of the maximum average degree of a subgraph, and thus is a measure of whether “local” density exists. For example, the arboricity of all minor-closed graphs is constant. The main result in this paper is a property tester for arboricity. Formally, the paper provides an algorithm that accepts if the graph is $$\varepsilon$$-close to having arboricity $$\alpha$$, and rejects if the graph is $$c\varepsilon$$-far from having arboricity $$3\alpha$$ (for large constant $$c$$). Ignoring dependencies on $$\varepsilon$$, the running time is $$O(n/\sqrt{m} + n\alpha/m)$$, which is proven to be optimal. The result builds on distributed graph algorithms for forest decompositions.The constant of $$3$$ can be brought down arbitrarily close to $$2$$, and it is an intriguing question if it can be reduced further.

On Approximating the Number of k-cliques in Sublinear Time, by Talya Eden, Dana Ron, and C. Seshadhri (arXiv). This paper studies the classic problem of approximating the number of $$k$$-cliques of a graph, in the adjacency list representation. The main result is an algorithm that $$(1+\varepsilon)$$-approximates $$C_k$$ (the number of $$k$$-cliques) in time $$O(n/C^k_k + m^{k/2}/C_k)$$. (This expression ignored polylogs and $$\varepsilon$$.) Somewhat surprisingly, this strange expression is the optimal complexity. It is a generalization of previous result of Goldreich-Ron (average degree/edge counting, $$k=2$$) and Eden et al (triangle counting, $$k=3$$). The algorithm is quite intricate, and is achieved by building on various sampling techniques in these results.

A characterization of testable hypergraph properties, by Felix Joos, Jaehoon Kim, Daniela Kühn, and Deryk Osthus (arXiv). A fundamental result of Alon, Fischer, Newman, and Shapira characterized all constant-time testable (dense) graph properties, through a connection to the regularity lemma. This paper essentially extends that characterization to $$k$$-uniform hypergraph properties. Essentially, the main results shows the testability of property $$\bf{P}$$ is equivalent to $$\bf{P}$$ being “regular-reducible”. This is a rather involved definition that captures properties where hypergraph regularity can be used for testing. Furthermore, this can also be used to prove that any testable property also has a constant-time distance estimation algorithm.

Distributed Testing of Conductance, by Hendrik Fichtenberger and Yadu Vasudev (arXiv). There has been recent interest in property testing in the distributed graph framework. The problem studied here in graph conductance. Specifically, we wish to accept a graph with conductance $$\Phi$$ and reject a graph that is far from having conductance $$\Phi^2$$. The setting is the CONGEST framework, where each vertex has a processor and can only communicate $$O(\log n)$$ amount of data to its neighbors in a single round. The main result gives an algorithm with $$O(\log n)$$ rounds, which is shown to be optimal. Standard testing algorithms for conductance basically perform a collection of random walks from some randomly chosen seeds vertices. An important insight in this paper is that testing algorithms for conductance can be simulated in the CONGEST model without having to maintain all the random walks explicitly. It suffices to transfer a small amount of information that tracks overall statistics of the walks, which suffice for the testing problem.

Improved bounds for testing Dyck languages, by Eldar Fischer, Frédéric Magniez, Tatiana Starikovskaya (arXiv). Testing membership in languages is a classic problem in property testing. Fix a language $$L$$ over an alphabet $$\Sigma$$. Given a string $$x$$ of length $$n$$, the tester should accept if $$x \in L$$ and reject if $$x$$ is far (in terms of Hamming distance) from $$L$$. This paper focuses the simple, yet fundamental setting of $$L$$ being a Dyck language, the set of strings of perfectly balanced parentheses. Let $$D_k$$ be the Dyck language using $$k$$ types of parentheses. The classic paper of Alon et al on regular language testing also gives a constant time tester for $$k=1$$, and subsequent work of Parnas, Ron, Rubinfeld proves, for $$k \geq 2$$, testing complexity bounds of $$O(n^{2/3})$$ and $$\Omega(n^{1/11})$$. This paper gives significant improvements in testing complexity: an upper bound of $$O(n^{2/5+\delta})$$ (for any $$\delta > 0$$) and a lower bound of $$\Omega(n^{1/5})$$. The lower bound proof introduces some new techniques for proving that similarity of transcript distributions of a deterministic algorithm over two distributions of inputs (the key step in any Yao’s minimax lemma application). The proof constructs a third transcript distribution using a special “wild” transcript that represents the (low probability) event of the algorithm “learning” too much. A careful construction of this distribution can used to upper bound the distance between the original transcript distributions.

News for April 2017

April was a busy month for property testing. A mixture of distribution testing, junta testing, Fourier transforms, matrix problems, and graph testing. Let’s go!
(Update: thanks to Omri Ben Eliezer for correcting some errors in our post. Also, he pointed out that we missed posting about by a property testing paper by Gishboliner-Shapira that appeared in Nov 2016.)

Fourier-Based Testing for Families of Distributions, by Clement Canonne, Ilias Diakonikolas, and Alistair Stewart (ECCC). Readers of PTReview will be familiar with great progress made over the past few years in distribution testing. We wish to determine some property $$\mathcal{P}$$ of a discrete distribution $$D$$ of support size $$n$$, using iid samples from the distribution. The challenge is that the number of samples should be $$o(n)$$. This paper gives a general framework for any property $$\mathcal{P}$$, such that all members (distributions) have sparse Fourier transforms. One of the main tools is a tester for determining if $$D$$ has small Fourier support (and find the restriction to this support). This is a really neat unifying methods that subsumes much of the past work. Moreover, this method leads to new testers for a variety of classes of distributions, including that of multinomial distributions.

Testing from One Sample: Is the casino really using a riffle shuffle, by Constantinos Daskalakis, Nishanth Dikkala, and Nick Gravin (arXiv). This paper introduces a novel twist on distribution testing: suppose $$\mathcal{D}$$ was generated through a Markov Chain, and we only get to see a sequence of samples generated through a random walk. Observe that we do not have the classic iid assumption any more. What can be said now? There is a challenge in defining “closeness” of distributions, which is done by looking at the variation distance between sequences generated through random walks of a carefully chosen length. The focus is on identity testing in two different regimes. First, with no assumptions on the Markov chain, there are general results that take $$O(n)$$ queries (note that the Markov chain has size $$O(n^2)$$). Secondly, for special “sparse” Markov Chains such as various models of card shuffling, one can get the number of samples to be logarithmic in size of the state space. Thus, one effectively gets to see a single shuffle process (which is like a walk in a Markov Chain), and can still decide if it is generating a uniform distribution.

Settling the query complexity of non-adaptive junta testing, by Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, and Jinyu Xie (arXiv). Ah, progress on a classic open problem! A function $$f:\{0,1\}^n \to \{0,1\}$$ is a $$k$$-junta if it only depends on $$k$$ variables. After a long line of work, Blais provided a non-adaptive $$\widetilde{O}(k^{3/2})$$ tester and in a separate result of Blais gave an adaptive (ignoring $$\epsilon$$ factors) $$\widetilde{O}(k)$$ tester. Previous to this paper, the best non-adaptive lower bound was essentially $$\Omega(k)$$, ignoring polylog factors. This paper finally provides a matching non-adaptive lower bound of $$\Omega(k^{3/2})$$, up to polylog factors! This basically settles the knowledge (adaptive and non-adaptive) of this problem, up to polylogs.

An Adaptive Sublinear-Time Block Sparse Fourier Transform, by Volkan Cevher, Michael Kapralov, Jonathan Scarlett, and Amir Zandieh (arXiv).
(We should have caught this when it was first published in Feb 2017, but at least we caught the update!) Consider a vector $$X$$ whose Fourier transform we wish to compute. Suppose there are only $$k$$ non-zero coefficients (typically, this is what we care about). We can actually compute these coefficients using $$O(k\log n)$$ queries, which is strongly sublinear when $$k \ll n$$. An important question is when the sample complexity can go below $$k\log n$$, which is optimal in general. Often sparsity Fourier coefficients have structure that can be exploited. This paper studies block-sparsity, where all non-zero coefficients occur in $$k_0$$ contiguous blocks (in Fourier space) of size $$k_1$$. Thus, the total sparsity is $$k = k_0k_1$$. This paper designs an algorithm with adaptive query complexity $$O(k_0k_1 + k_0\log n)$$, thereby circumventing the $$k\log n$$ barrier for $$k_0 \ll k$$. Interestingly, the paper gives lower bounds showing that adaptivity is necessary for removing the $$\log n$$ factor.

Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices, by Cameron Musco and David P. Woodruff (arXiv). Few problems occur as often as computing a low-rank approximation of a matrix $$A$$. Formally, one wishes to compute a rank $$k$$-matrix $$B$$ such that $$\|A-B\|_F$$ is minimized. SVD is the obvious method to do this, but is computationally expensive. There are a number of sampling methods, but all of them require reading all of $$A$$. This paper gives a truly sublinear-time algorithm (for small $$k$$) for PSD matrices. Formally, the algorithm presented here requires $$O(n \cdot \mathrm{poly}(k))$$ running time, where $$n$$ is the dimension size of $$A$$. It is well-known from previous work that there exist a subset of $$k$$ columns that form a good low-rank approximation. Yet finding them requires reading the whole matrix to compute various sampling strategies. The intuition here is that large entries cannot “hide” in arbitrary locations in a PSD matrix.

Testing hereditary properties of ordered graphs and matrices, by Noga Alon, Omri Ben-Eliezer, and Eldar Fischer (arXiv). Classic results by Alon-Shapira and Alon-Fischer-Newman-Shapira have shown that hereditary graph properties are testable in constant time. There is a deep connection between testing such properties and the existence of subgraph removal lemmas. The latter assert that, given some family $$\mathcal{F}$$ of forbidden subgraphs, if an $$n$$-vertex graph is $$\epsilon$$-far from being $$\mathcal{F}$$-free, then it must contain $$\delta n^q$$ copies of some $$F \in \mathcal{F}$$ (where $$F$$ has $$q$$ vertices, $$\delta$$ is a function only of $$\epsilon$$). This paper generalizes these theorems to general matrices over finite domains and ordered edge-colored graphs, where vertices in the graphs have a fixed ordering. Thus, one does not require the symmetry (over isomorphism) of graph properties for testability. These theorems lead to testability results for large classes of properties defined through forbidden substructures.

Removal Lemmas with Polynomial Bounds, by Lior Gishboliner and Asaf Shapira (arXiv). (Paper originally appeared in Nov 2016, but we missed it.) As mentioned above, there is a close connection between property testing of dense graphs and graph removal lemmas. Yet the property testers that result from these lemmas, like the celebrated triangle removal lemma, have terrible tower-like dependences on the parameter $$\epsilon$$. When can we get polynomial dependences on $$\epsilon$$ (which is called “easy testability”)? This fundamental question is answered in this paper. Consider the case when $$\mathcal{F}$$ is finite. If $$\mathcal{F}$$ contains a bipartite graph, the complement of a bipartite graph, and a split graph, then there are polynomially bounded graph removal lemmas (and hence easy property testers) for this family. Furthermore, one cannot drop any of these requirements! (A split graph is one where vertices can be partitioned into a set spanning a clique, and a set spanning an independent set.) There are generalizations to infinite families of graphs. An important corollary of this result is a proof of easy testability of semi-algebraic properties. This captures properties of graphs where vertices are points in Euclidean space and edges are present when the points satisfy some polynomial constraint (in the coordinates).

News for January 2017

2017 starts off rather slow for property testing. Though, we have an intriguing paper to report – an experimental analysis of a classic sublinear algorithm.

Evaluating a Sublinear-time Algorithm for the Minimum Spanning Tree Weight Problem, by Gabriele Santi and Leonardo De Laurentiis (arXiv). The Chazelle-Rubinfeld-Trevisan Minimum Spanning Tree algorithm is a classic in sublinear algorithms. This algorithms provides a $$(1+\varepsilon)$$ approximation to the MST in time independent of the number of vertices (although it does depend on the average degree). But how this compare with Prim’s algorithm on real instances, in a real (not theoretical) computer? This intriguing paper does a detailed experimental comparison. Having done experimental graph algorithms myself, I can attest to the various challenges: how to choose a test set of graphs? How to set error parameters? Can data structure optimization on the coding side beat asymptotic improvements? This paper does a series of experiments on synthetic graph generators (such as Erdős-Rényi, Barabási-Albert, Watts-Strogatz models). They do validate the basic CRT algorithm at scale, by showing that it is faster than Prim for graphs with more than a million edges. Their experiments suggest that the sublinear-time algorithm gives little benefits when $$\varepsilon \leq 0.2$$. The paper has many experiments for a variety of settings, and the authors do a comprehensive study of the various parameters. I’d definitely recommend to anyone interested in exploring how property testing might influence algorithms in the real world.

News for October 2016

Alas, a rather dry month for property testing. We did find one quantum computing result based on the classic linearity testing theorem.

Robust Self-Testing of Many-Qubit States, by Anand Natarajan and Thomas Vidick (arXiv). (Frankly, my understanding of quantum computation is poor, and this summary may reflect that. Then again, some searching on Google and Wikipedia have definitely broadened my horizons.) One of the key concepts in quantum computation is the notion of entanglement. This allows for correlations between (qu)bits of information beyond what can be classically achieved. Given some device with supposed quantum properties (such as sets of entangled bits), is there a way of verification by measuring various outcomes of the device? This is referred to as self-testing of quantum states. This paper proves such a result for a set of $$n$$ EPR pairs, which one can think of $$n$$ pairs of “entangled” qubits. The interest to us property testers is the application of a quantum version of the seminar Blum, Luby, Rubinfeld linearity test.

News for July 2016

After a few slow months, property testing is back with a bang! This month we have a wide range on results ranging from classic problems like junta testing to new models of property testing.

Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism, by Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, and Dana Ron (arXiv). The problem of junta testing requires little introduction. Given a boolean function $$f:\{-1,+1\}^n \mapsto \{-1,+1\}$$, a $$k$$-junta only depends on $$k$$ of the input variables. A classic problem has been that of property testing $$k$$-juntas, and a rich line of work (almost) resolves the complexity to be $$\Theta(k/\epsilon)$$. But what of tolerant testing, where we want to tester to accept functions close to being a junta? Previous work has shown that existing testers are tolerant, but with extremely weak parameters. This paper proves: there is a $$poly(k/\epsilon)$$-query tester that accepts every function $$\epsilon/16$$-close to a $$k$$-junta and rejects every function $$\epsilon$$-far from being a $$4k$$-junta. Note that the “gap” between the junta classes is a factor of 4, and this is the first result to achieve a constant gap. The paper also gives testers when we wish to reject functions far from being a $$k$$-junta (exactly matching the definition of tolerant testng), but the tester has an exponential dependence on $$k$$. The results have intriguing connections with isomorphism testing, and there is a neat use of constrained submodular minimization.

Testing Pattern-Freeness, by Simon Korman and Daniel Reichman (arXiv). Consider a string $$I$$ of length $$n$$ and a “pattern” $$J$$ of length $$k$$, both over some alphabet $$\Sigma$$. Our aim is to property test if $$I$$ is $$J$$-free, meaning that $$I$$ does not contains $$J$$ as a substring. This problem can also be generalized to the 2-dimensional setting, where $$I$$ and $$J$$ are matrices with entries in $$\Sigma$$. This formulation is relevant in image testing, where we need to search for a template pattern in a large image. The main results show that these testing problems can be solved in time $$O(1/\epsilon)$$, with an intriguing caveat. If the pattern $$J$$ has at least $$3$$ distinct symbols, the result holds. If $$J$$ is truly binary, then $$J$$ is not allowed to be in a specified set of forbidden patterns. The main tool is a modification lemma that shows how to “kill” a specified occurrence of $$J$$ without introducing a new one. This lemma is not true for the forbidden patterns, resulting in the dichotomy of the results.

Erasure-Resilient Property Testing, by Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, and Nithin Varma (arXiv). Property testing begins with a query model for $$f: \mathcal{D} \mapsto \mathcal{R}$$, so we can access any $$f(x)$$. But what if an adversary corrupted some fraction of the input? Consider monotonicity testing on the line, so $$f: [n] \mapsto \mathbb{R}$$. We wish to test if $$f$$ is $$\epsilon$$-far from being monotone, but the adversary corrupts/hides an $$\alpha$$-fraction of the values. When we query such a position, we receive a null value. We wish to accept if there exists some “filling” of the corrupted values that makes $$f$$ monotone, and reject if all “fillings” keep $$f$$ far from monotone. It turns out the standard set of property testers are not erasure resilient, and fail on this problem. This papers gives erasure resilient testers for properties like monotonicity, Lipschitz continuity, and convexity. The heart of the techniques involves a randomized binary tree tester for the line that can avoid the corrupted points.

Partial Sublinear Time Approximation and Inapproximation for Maximum Coverage, by Bin Fu (arXiv). Consider the classic maximum coverage problem. We have $$m$$ sets $$A_1, A_2, \ldots, A_m$$ and wish to pick the $$k$$ of them with the largest union size. The query model allows for membership queries, cardinality queries, and generation of random elements from a set. Note that the size of the input can be thought of as $$\sum_i |A_i|$$. Can one approximate this problem without reading the full input? This paper gives a $$(1-1/e)$$-factor approximation that runs in time $$poly(k)m\log m$$, and is thus sublinear in the input size. The algorithm essentially implements a greedy approximation algorithm in sublinear time. It is shown the the linear dependence on $$m$$ is necessary: there is no constant factor approximation that runs in $$q(n) m^{1-\delta}$$ (where $$n$$ denotes the maximum cardinality, $$q(\cdot)$$ is an arbitrary function, and $$\delta > 0$$).

Local Testing for Membership in Lattices, by Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, and Elena Grigorescu (arXiv). Inspired by the theory of locally testable codes, this paper introduces local testing in lattices. Given a set of basis vectors $$b_1, b_2, \ldots$$ in $$\mathbb{Z}^n$$, the lattice $$L$$ is the set of all integer linear combinations of the basic vectors. This is the natural analogue of linear error correcting codes (where everything is done over finite fields). Given some input $$t \in \mathbb{Z}^n$$, we wish to determine if $$t \in L$$, or is far (defined through some norm) from all vectors in $$L$$, by querying a constant number of coordinates in $$t$$. We assume that $$L$$ is fixed, so it can be preprocessed arbitrarily. This opens up a rich source of questions, and this work might be seen as only the first step in this direction. The papers shows a number of results. Firstly, there is a family of “code formula” lattices for which testers exists (with almost matching lower bounds). Furthermore, with high probability over random lattices, testers do not exist. Analogous to testing codes, if a constant query lattice tester exists, then there exists a canonical constant query tester.

News for June 2016

This month isn’t the most exciting for property testing. Just one paper to report (thanks to Clément for catching!), of which only a minor part is actually related to property testing.

Approximating the Spectral Sums of Large-scale Matrices using Chebyshev Approximation, by Insu Han, Dmitry Malioutov, Haim Avron, and Jinwoo Shin (arXiv). The main results of the paper deal with approximating the trace of matrix functions. Consider symmetric matrix $$M \in \mathbb{R}^{d\times d}$$, with eigenvalues $$\lambda_1, \lambda_2, \ldots, \lambda_d$$. The paper gives new algorithms to approximate $$\sum_i f(\lambda_i)$$. Each “operation” of the algorithm is a matrix-vector product, and the aim is to minimize the number of such operations. The property testing application is as follows. Suppose we wish to test if $$M$$ is positive-definite (all $$\lambda_i > 0$$). We consider a matrix $$\epsilon$$-far from being positive-definite if the smallest eigenvalue is less than $$-\epsilon \|M\|_F = -\epsilon \sum_i \lambda^2_i$$. The main theorems in this paper yield a testing algorithm (under this definition of distance) that makes $$o(d)$$ matrix-vector products. While this is not exactly sublinear under a standard query access model, it is relevant when $$M$$ is not explicitly represented and the only access is through such matrix-vector product queries.

Welcome Clément and Gautam!

Dear readers, please welcome the new additions to our moderator group, Clément Canonne and Gautam Kamath! It’s great that more property testing researchers are helping take PTReview further. PTReview is becoming really popular these days! (Or so we hope…)