In the first month of 2016 we had a couple of interesting papers in property testing.

Sublinear-Time Algorithms for Counting Star Subgraphs with Applications to Join Selectivity Estimation by Maryam Aliakbarpour, Amartya Shankha Biswas, Themistoklis Gouleakis, John Peebles, Ronitt Rubinfeld and Anak Yodpinyanee (ArXiv) . Estimating the number of subgraphs of a fixed form in a given graph has been a very well studied problem in the subject of property testing.  The classical example is counting the number of triangles in a graph. Usually we assume we can sample the vertices uniformly at random. In this paper a new model of query has been considered where one can sample the edges uniformly at random. Under this model it is shown that the query complexity can be reduced when the goal is to estimate the number of p-stars in a graph. It would be interesting to see if this model helps to get better query complexity for other problems also. Depending on the application different query models can be relevant and hence understanding these different query models are essential.

A New Approach for Testing Properties of Discrete Distributions by Ilias Diakonikolas and Daniel M. Kane (ArXiv) . Testing properties of distribution has been a central topic in our field. Not only are these problems interesting they also has been applied as subroutines to many other testing algorithms. In the literature a number of different properties like testing whether a distribution is uniform or testing whether two distributions are identical or testing if two distributions are independent and many more has been studied. In most of the properties the distance measure is the L_1 measure. In this paper a unifying technique to obtain testing algorithms for properties of distributions in the L_1 distance has been given by converting them to the problem of testing in the L_2 distance and applying standard testing algorithms in the L_2 distance. This approach would hopefully help us simplify the various algorithms in distribution testing.