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.