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.

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.