Three papers this month close out Summer 2018.

Test without Trust: Optimal Locally Private Distribution Testing, by Jayadev Acharya, Clément L. Canonne, Cody Freitag, and Himanshu Tyagi (arXiv). This work studies distribution testing in the local privacy model. While private distribution testing has recently been studied, requiring that the algorithm’s output is differentially private with respect to the input dataset, local privacy has this requirement for each individual datapoint. The authors prove optimal upper and lower bounds for identity and independence testing, using a novel public-coin protocol named RAPTOR which can outperform any private-key protocol.

Testing Graph Clusterability: Algorithms and Lower Bounds, by Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, and Yuval Peres (arXiv). This paper studies the problem of testing whether a graph is \(k\)-clusterable (based on the conductance of each cluster), or if it is far from all such graphs — this is a generalization of the classical problem of testing whether a graph is an expansion. It manages to solve this problem under weaker assumptions than previously considered. Technically, prior work embedded a subset of the graph into Euclidean space and clustered based on distances between vertices. This work uses richer geometric structure, including angles between the points, in order to obtain stronger results.

Near log-convexity of measured heat in (discrete) time and consequences, by Mert Saglam (ECCC). Glancing at the title, it might not be clear how this paper relates to property testing. The primary problem of study is the quantity \(m_t = uS^tv\), where \(u, v\) are positive unit vectors and \(S\) is a symmetric substochastic matrix. This quantity can be viewed as a measurement of the heat measured at vector \(v\), after letting the initial configuration of \(u\) evolve according to \(S\) for \(t\) time steps. The author proves an inequality which roughly states \(m_{t+2} \geq t^{1 – \varepsilon} m_t^{1 + 2/t}\), which can be used as a type of log-convexity statement. Surprisingly, this leads to lower bounds for the communication complexity of the \(k\)-Hamming problem, which in turns leads to optimal lower bounds for the complexity of testing \(k\)-linearity and \(k\)-juntas.