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

Helly-Type Theorems in Property Testing by Sourav Chakraborty, Rameshwar Pratap, Sasanka Roy, and Shubhangi Saraf (arXiv). Helly’s Theorem states that if every \(d+1\) sets in a family \(F\) of convex sets in \(\mathbb{R}^d\) have non-empty intersection, then the intersection of the whole family \(F\) is also non-empty. This paper establishes a new connection between Helly’s theorem and clustering problems. Specifically, extensions of Helly’s theorem are used to analyze algorithms that test whether a set of points can be partitioned into a small number of clusters or not.

On active and passive testing by Noga Alon, Rani Hod, and Amit Weinstein (arXiv). In the standard property testing setting, the tester is able to query any input it chooses. This model is unrealistic in some settings, where instead it is more appropriate to consider models where the tester can only choose queries from a restricted set of the inputs (active testing) or where the tester only sees bits sampled at random from the input (passive testing). This paper gives new upper and lower bounds on the number of queries required to test many natural properties of boolean functions—including juntas, partially symmetric functions, and low degree polynomials—in these two settings.

Explicit Maximally Recoverable Codes with Locality by Parikshit Gopalan, Cheng Huang, Bob Jenkins, and Sergey Yekhanin (ECCC). The central goal in the study of locally decodable codes is to maintain the rate and error tolerance while adding the condition that we can recover any bit of the original input with a small number of queries to the codeword. This paper considers and makes progress on an interesting relaxation of this problem: here the goal is to maintain local decoding when a small number of errors are introduced, while allowing more queries to be made to decode input bits when more errors occur.

In June, we had a property testing workshop at Haifa where a lot of recent PT work was discussed. Check out the post on that. June also saw some interesting developments on testing affine-invariant properties, on testing sub-properties, on local computation algorithms, and on PCP constructions.

TESTING AFFINE-INVARIANT PROPERTIES

Over the last few years, there has been much progress in determining which affine-invariant properties of boolean functions can be tested with a constant number of queries. In Estimating the distance from testable affine-invariant properties (arXiv, ECCC), Hamed Hatami and Shachar Lovett show that for every such property, we can not only test it but also estimate the distance to the property with a constant number of queries.

The function linear isomorphism testing problem asks: How many queries do we need to test if a given (unknown) function is equivalent, up to a linear transformation of the input space, to some (known) function \(f\)? The answer to this question depends on the choice of the function \(f\). Elena Grigorescu, Karl Wimmer, and Ning Xie, in Tight lower bounds for testing linear isomorphism (ECCC) and Abhishek Bhrushundi, in the concurrent and independent paper On testing bent functions (ECCC), show that the query complexity for testing linear isomorphism is maximized when \(f\) is the Inner Product function. Interestingly, the proofs of this result (and other more general results) are obtained using completely different methods: Elena, Karl, and Ning prove their lower bounds using the communication complexity method, while Abhishek’s proof is obtained by studying the parity decision tree complexity of boolean functions.

TESTING SUB-PROPERTIES

One counter-intuitive aspect of property testing is that the query complexity for testing \(P\) does not in general imply anything about the query complexity for testing a sub-property \(P’ \subseteq P\). For example, while we can test halfspaces (aka, linear threshold functions) with a constant number of queries, testing the subclass of signed majorities is known to require \(\Omega(\log n)\) queries, and in fact the best-known algorithm for this task is a non-adaptive tester that requires \(O(\sqrt{n})\) queries. In Exponentially improved algorithms and lower bounds for testing signed majorities (ECCC), Dana Ron and Rocco Servedio dramatically improve both the upper and lower bounds: they show that non-adaptive algorithms for testing signed majorities require \(\mathrm{poly}(n)\) queries and that signed majorities can be tested by an adaptive algorithm that requires only \(\mathrm{polylog}(n)\) queries.

Another phenomenon that appears in some natural properties is that while a property \(P\) requires many queries to test, it can be partitioned into (slightly) smaller properties \(P’\) that can each be tested with a constant number of queries. It is natural to ask whether this is a universal phenomenon. In Some properties are not even partially testable (arXiv, ECCC), Eldar Fischer, Yonatan Goldhirsh, and Oded Lachish show that it is not: they show that there are properties \(P\) for which every (large enough) sub-property of \(P\) requires a large number of queries to test.

LOCAL COMPUTATION AND PCP CONSTRUCTIONS

A notion that is very closely related to property testing is that of local computation
algorithms: algorithms that, as in the property testing setting, aim to compute the solution of a problem in sublinear time by querying as few bits of the input as possible. In A Local Computation Approximation Scheme to Maximum Matching (arXiv), Yishay Mansour and Shai Vardi give a new local computation algorithm for obtaining a \((1-\epsilon)\)-approximation to the maximum matching in bounded-degree graphs.

The notion of Probabilistically Checkable Proofs (PCPs) is also closely related to property testing, where now the input to the tester is a string \(x\) and a purported proof that \(x\) satisfies some property \(P\); the tester must verify the correctness of the proof while examining as few bits of \(x\) and of the proof as possible. A long-standing open problem in this area is to understand the best possible trade-offs between the query complexity and the length of proofs for PCP constructions. In Constant rate PCPs for circuit-SAT with sublinear query complexity (ECCC), Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, and Henning Stichtenoth give a verifier for a special case of PCPs that obtains a sublinear query complexity with proofs that have length only linear in the size of the input.