May seems to be a slow month for property testing, with only one paper on locally testable codes. Nonetheless, we have unearthed a paper from April (missed despite our best efforts) on a related topic of hidden set approximations.

The Power of an Example: Hidden Set Size Approximation Using Group Queries and Conditional Sampling by Dana Ron and Gilad Tsur (arXiv). Consider a known universe \(U\) and an unknown subset \(S\). Our aim is to approximately determine \(|S|\). We can perform subset queries: for a query subset \(T\), an oracle returns whether \(T \cap S \neq \emptyset\) or (a more powerful model) the oracle returns a uniform random element in \(T \cap S\). This paper gives a detailed study of this problem under various settings. There is a fascinating array of upper and lower bounds, including situations where \(U\) is ordered and \(T\) must be an interval, the difference between adaptivity and non-adaptivity, arbitrary subset queries, and much more. The topic seems to be quite rich, and it should yield some nice sets of problems to study further. It appears that some lower bounds are quite open. Students, pay attention!

Limitations on Testable Affine-Invariant Codes in the High-Rate Regime by Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, and Carol Wang (ECCC). Locally Testable Codes (LTCs) are codes that (typically) have a constant time tester. Interestingly, recent work on testing codes using a linear number of queries (some small constant fraction of the code length) has connections to the Small Set Expansion (SSE) problem, which in turn is related to the famous Unique Games Conjecture (UGC). A paper by Barak et al. gives a construction of a small set expander (a graph where all small sets have high conductance) where the Laplacian has many small eigenvalues (so it’s “difficult” to find a low conductance cut). This construction uses high-rate LTCs that are linear time testable. In some sense, the better the rate, the better construction one gets. This paper asks how far this idea can go. So the idea is to construct the best rate linear-time testable LTC. Reed-Muller codes fall in this category, but their rate is quite far from optimal. Recent work by Guo et al. gives a slightly better construction, but this is far from the (near) optimal rate achieved by BCH codes (which are not known to be testable). All in all, this paper shows that for affine-invariant codes, the Guo et al. construction is essentially the best testable high-rate code one can get. I have obviously done no justice to the depth of the connections, the intricacies of the parameters, or the overall coolness of this subject. So go read the paper!

As winter finally releases its grip here on the east coast, we celebrate with forests, with bounded-derivative properties, and with hypergraphs. (I believe these are the traditional ingredients for the beginning-of-spring celebrations in New England, but I could be wrong.)

Testing Forest-Isomorphism in the Adjacency List Model by Mitsuru Kusumoto and Yuichi Yoshida (arXiv). Which properties of sparse graphs can we test efficiently? To a large extent, this fundamental question remains open. The natural setting in which to study this question is the adjacency list query model. In this model, a testing algorithm can select any vertex \(v\) and index \(i\); it then receives the identity \(w\) of the \(i\)th neighbor of \(v\). Kusumoto and Yoshida show that in this model, we can test if two forests (i.e., collections of trees) on \(n\) vertices are identical up to relabeling of the vertices with polylog(\(n\)) queries. They also show that, remarkably, this tester can be used to test any property of forests in the adjacency list model with polylog(\(n\)) queries.

Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties by Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, and C. Seshadhri (arXiv). Two basic properties of a function \(f : [n]^d \to \mathbb{R}\) on the hypergrid are monotonicity and the Lipschitz property. These two properties are special cases of a more general class of properties called bounded-derivative properties. In this paper, the authors give optimal bounds on the number of queries required to test these properties over every product distribution on the hypergrid. These results are obtained by deriving new dimension-reduction results and, most interestingly, by establishing and exploiting a strong connection between bounded-derivative properties and binary search trees.

Any Monotone Property of 3-uniform Hypergraphs is Weakly Evasive by Raghav Kulkarni, Youming Qiao, and Xiaoming Sun (ECCC). What happens if we remove the distance promise in the definition of property testing? Or, equivalently, how efficient can testers be if they must distinguish objects with some property \(P\) from every object that does not have the property \(P\)? The answer to this question seems completely obvious: no non-trivial property can be tested in this setting with a sublinear number of queries. We can easily verify that this answer is indeed correct for our favorite properties… but is it really true for every non-trivial property? As it turns out, this question is far from trivial, and in fact leads to the famous evasiveness conjectures and to the celebrated results of Rivest and Vuillemin and of Kahn, Saks, and Sturvevant. The current paper combines and extends ideas from both of these papers to show that deterministic testers for any monotone non-trivial property of 3-uniform hypergraphs indeed have linear query complexity.

On Learning and Testing Dynamic Environments by Oded Goldreich and Dana Ron (ECCC). Given a dynamic environment that is evolving according to a local rule, the goal is to query some of the states in the system at some point of time and determine if the system is evolving according to some fixed rule or is far from it. A harder problem is to learn the evolution of the environment. They give some upper and some lower bounds for various versions of these problems. In particular they show that using sub-linear queries a lot can be achieved even in this setting. This is the first of its kind result and possibly many more results in this area will follow soon.

So what did we see in February 2014?

Local Algorithms for Sparse Spanning Graphs by Reut Levi, Dana Ron, and Ronitt Rubinfeld (arXiv). Given a graph \(G = (V,E)\), the aim is the find a small sparse spanning subgraph \(G’\) in the local algorithm setting. So, given any edge \((u,v) \in E\), we must determine in sublinear time whether this edge exists in \(G’\). The main result is an \(\Omega(|V|)\) lower bound, and a matching algorithm when \(G\) is either an expander or hyperfinite.

A Characterization of Locally Testable Affine-Invariant Properties via Decomposition Theorems by Yuichi Yoshida (arXiv). This result gives a complete characterization of (two-sided) locally testable affine-invariant properties. These are based on existing decomposition theorems for functions into structured and pseudorandom parts. This result is analogous to that of Alon, Fischer, Newman, and Shapira (link) on characterizations for testability over dense graphs.

Testing probability distributions underlying aggregated data by Clément Canonne and Ronitt Rubinfeld (arXiv). There has been much recent work on distribution testing, and this work discusses stronger models where better algorithms can be obtained. Given a distribution \(D\) over \([n]\), we can get samples from this distribution, and also query the probability \(D(i)\) of any \(i \in [n]\). With these “dual” queries, one gets distribution testers for a variety of problems surpassing previous lower bounds. Interestingly, this is stronger than the conditional model introduced recently (here and here).

Strong Locally Testable Codes with Relaxed Local Decoders by Oded Goldreich, Tom Gur, and Ilan Komargodski (ECCC). For a locally testable code (LTC), the property of being a codeword is efficiently (constant time) testable. A locally decodable code (LDC) is a code from which individual bits of the original message can be recovered in constant time. A relaxed local decoder is allowed to declare failure for recovered a small fraction of message bits. This allows for bypassing the difficult (and prominent) open problem of constructing small LDCs. This result gives a construction of near-linear LTCs with a relaxed local decoder. This result leads to a property that is hard to test but easy to verify (in the MA proofs of proximity sense, refer to last month’s open problem).

As we already covered in earlier posts, quite a few notable property testing papers were presented at the SODA and ITCS conferences this month. In addition, an exciting new set of results on a variant of the linearity testing problem was also posted on ECCC.

Direct Sum Testing by Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, and Igor Shinkar. One of the true gems of property testing is the linearity testing: as Blum, Luby, and Rubinfeld first showed, we can test whether a boolean function is linear with a (very natural) 3-query test. A fascinating variant of this problem that is still largely open to this day is the following: is linearity still testable even when we consider functions defined on a subset of the hypercube? This paper considers the problem when the subsets in question are layers of the hypercube, a problem that is closely connected to PCP constructions and direct sum operations on multi-player games. The main result of the paper shows that we can also test linearity for functions defined on layers of the hypercube with a natural 3-query tester.

Here’s a report on the new papers we saw in December 2013.

Property Testing on Linked Lists by Peyman Afshani, Kevin Matulef and  Bryan T. Wilkinson (ECCC). Monotonicity testing has been an important problem for past many years. In the usual settings either the input is accessed by random sampling or the input is given in an easy to access form (like an array). In this paper they have consider a model which is somewhere in the middle of the other two models. Here the input is given as an linked list. They have shown that, in this model, monotonicity testing requires Θ(n^{1/3}) queries.

Direct Product Testing by Irit Dinur and David Steurer (ECCC).  In this paper they have considered the problem “Does there exist a two-query test that distinguishes between direct products and functions that are far from direct products with constant probability?” This is a very important problem that has application in gap amplification in PCP. They answer the question in the affirmative.

Property-Testing in Sparse Directed Graphs: 3-Star-Freeness and Connectivity by  Frank Hellweg and Christian Sohler (ArXiv).  There are different models, for querying, in the case of property testing in sparse directed graphs.  In one such model, proposed by Bender and Ron, only the outgoing edges are queried.  In this paper upper bounds on the query complexity for testing subgraph freeness and strong connectivity has been obtained.

High Dimensional Expanders and Property Testing by Tali Kaufman and Alexander Lubotzky (ArXiv).   Expanders have always played an important role in property testing. Usually expanders are either used for designing testers or proving correctness of testers. We sometimes test for expansion property also. In this paper they have linked expansion property of some structure to testability of some other property. They study the higher dimensional expansion property, as studied by Gromov, Linial and Meshulam. They show that a simplicial complex is a high dimensional expander if and only if a suitable property is testable.

The action in November is mainly in algebraic property testing.

On Testing Affine-Invariant Properties by Arnab Bhattacharyya (ECCC). As mentioned here, Arnab put together an excellent survey on testing, ahem, affine-invariant properties. It gives a great overview of this area for a non-expert, and is highly recommended for anyone wanting to get a sense of the existing results and open problems.

Algorithmic Regularity for Polynomials and Applications by Arnab Bhattacharyya, Pooya Hatami, and Madhur Tulsiani (Arxiv). Not a pure property testing paper per se. But you can’t complain about papers related to regularity lemmas in a property testing blog. Think of the Szemerédi regularity lemma as the following: given any partition of a graph, one can “refine” it, so that the resulting partition has “few” pieces and is “regular”. Analogously, the regularity lemma for polynomials says that given any set of polynomials, one can “refine” it to get a “small regular” set of polynomials. This has direct applications in Reed-Muller testing (there’s your property testing connection!). This paper is on giving an algorithm that actually constructs this regular set of polynomials. Among other things, this algorithm can be used in decoding of Reed-Muller codes beyond the list-decoding radius.

We saw two new property testing papers in October. During the month, we also saw a great presentation on estimating the distance to testable affine-invariant properties (discussed here) at FOCS, and we saw some intriguing property testing papers in the list of accepted papers for ITCS 2014.

Survey on Quantum Property Testing by Ashley Montanaro and Ronald de Wolf (arxiv). We already mentioned this survey here, but it is worth discussing it again. With a clear presentation of fundamental results in the area, this survey is a great reference for any researcher in property testing or in quantum complexity that wants to learn about the intersection of the two fields. And with 12 open questions presented throughout the text, this is also the ideal starting point for any researcher who wants to jump into the area.

Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees by Abhishek Bhrushundi, Sourav Chakraborty, and Raghav Kulkarni (ECCC). The authors observe that the problem of testing a property \(P\) of linear or quadratic boolean functions is equivalent to determining the parity decision tree complexity of a function \(f\) determined by \(P\). This connection is used to obtain strong lower bounds on the query complexity required to test \(k\)-linearity, bent functions, and other related properties. It also provides further motivation for the the study of parity decision trees and the related problems on the Fourier structure of boolean functions.

Here’s a report on the new papers we saw in September. The list of accepted papers in SODA 2014 also came out in September. While we have covered one of the accepted papers in our “News for August 2013″ post we look at two more accepted paper in this post.

Non-Interactive Proofs of Proximity by Tom Gur and Ron D. Rothblum (ECCC). In a proof-systems a verifier tries to ascertain the validity of a statement by using the help of a proof. PCP, PCPP are classical examples of proof-systems. The kind of access a verifier has to the statement and the proof determines the power of the proof system. This paper considers the proof system when the verifier has full access to the proof (which is sub-linear) and oracle access to the statement. And the goal of the verifier is to accept a valid statement and reject a statement that is far from true while optimizing the queries to the statement. This paper tries to understand the power of this proof system (in terms of query complexity) in comparison to other proof systems.

Testing Surface Area by Pravesh Kothari, Amir Nayyeri, Ryan O’Donnell and Chenggang Wu (accepted in SODA 2014) [preprint].  Estimating the surface area of a set  F ⊆ Rⁿ given point-query access is a very fundamental problem in geometry. Usually one assumes some structure on the surface for estimating the area, like convexity. This paper considers general surface areas and the goal is to distinguish the case when the surface area is less than A from the case when the surface is far from having a surface area less than κA (κ a parameter ≥1). In the 1, 2 or 3 dimension constant query algorithm is obtained for certain κ.

A connection between surface area and noise sensitivity by Joe Neeman (ArXiv). This paper also considers the problem of estimating the surface area of a set. It improves some of the results from the above mentioned paper – “Testing Surface Area” by Pravesh Kothari, Amir Nayyeri, Ryan O’Donnell and Chenggang Wu.

Testing equivalence between distributions using conditional samples by Clement Canonne, Dana Ron and Rocco A. Servedio (accepted in SODA 2014) [preprint]. Testing whether two distributions are equivalent is an important and well studied problem. Usually a distribution is accessed by drawing random samples according to the distribution. But other variants of how to access the distributions has also been studied. One such is the conditional query: here one can specify a set S and draws a random sample according to the distribution conditioned on the fact that outcome comes from S.  This paper shows that conditional queries can help in improving the query complexity by an exponential amount (or more) for testing equivalence of distributions (both when one distribution is known and when none of them are known). Some restricted versions of conditional queries (where the size of S is fixed) have also been studied.

August saw a couple of conferences: RANDOM-APPROX and a seminar at the Simon’s institute. Here’s a report on the new papers we saw in August, including much progress on distribution testing.

On sample based testers by Oded Goldreich and Dana Ron (ECCC).The usual setting for property testing is beloved query model, where the tester gets to make any query it pleases. A much weaker setting would be to simply get random (labeled) samples of the domain. These are called sample based testers, and are more akin to setting in learning theory. Sampled based testers were also discussed in the seminal Goldreich, Goldwasser, and Ron paper. Since then, there have been variants, such as distribution-free testing and active testing. In this paper, it is shown that constant-query proximity-oblivious testers imply the existence of sublinear (polynomial dependence in size) sample based testers.

Instance-by-instance optimal identity testing by Gregory Valiant and Paul Valiant (ECCC). The problem of distribution testing is a problem that we all love. Given a known discrete distribution \(p\), we wish to test equality (with \(p\)) of an unknown distribution \(q\). How many independent samples are required of \(q\)? This paper gives an optimal algorithm for each distribution \(p\), subsuming much past work. The analysis involves a characterization of Hölder and norm-monotonicity type inequalities. Definitely on my list to read!

Optimal algorithms for testing closeness of discrete distributions by Siu-On Chan, Ilias Diakonikolas, Gregory Valiant, Paul Valiant (Arxiv). Now consider the setting where both \(p\) and \(q\) are unknown (over a support of size \(n\)), and we wish to test equality. (We define “far” in terms of variation distance.) A (by-now) classic paper of Batu et al. gives an \(O(n^{2/3}\log n/\varepsilon^{8/3})\) and Valiant proved an \(\Omega(n^{2/3})\) lower bound. This paper completely resolves this problem problem with an algorithm and matching lower bound of \(\max(n^{2/3}/\varepsilon^{4/3}, n^{1/2}/\varepsilon^2)\).