This was a relatively sleepy month with only two property testing papers. Do let us know if we missed any. Let us dig in. (EDIT: Two updates.)
- I missed two papers. One on the estimation of quantum entropies and the other on algorithms and lower bounds for estimating MST and TSP costs.
- Finally, I forgot to welcome our new editor. Welcome onboard, Nithin Varma!!
Private High-Dimensional Hypothesis Testing by Shyam Narayanan (arXiv) This paper continues the novel study of distribution testing under the constraints brought forth by differential privacy extending the work of Canonne-Kamath-McMillan-Ullman-Zakynthinou (henceforth CKMUZ, covered in our May 2019 post). In particular, the paper presents algorithms with optimal sample complexity for private identity testing of \(d\)-dimensional Gaussians. In more detail, the paper shows that can be done with a mere \(\widetilde{O}\left( \frac{d^{1/2}}{\alpha^2} + \frac{ d^{1/3} }{ \alpha^{4/3} \cdot \varepsilon^{2/3}} + \frac{1}{\alpha \cdot \varepsilon} \right)\). Here \(\alpha\) is the proximity parameter and \(\varepsilon\) is the privacy parameter. Combined with a previous result of Acharya-Sun-Zhang, the paper proves that private identity testing of \(d\)-dimensional Gaussians is doable with a sample complexity smaller than that of private identity testing of discrete distributions over a domain of size \(d\) thereby refuting a conjecture of CKMUZ.
Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds by Badih Ghazi, Ravi Kumar, Pasin Manurangsi and Jelani Nelson (arXiv) Adam Sealfon considered the classic All Pairs Shortest Path Problem (the APSP problem) with privacy considerations in 2016. In the \((\varepsilon, \delta)\)-DP framework, Sealfon presented an algorithm which on input an edge-weighted graph \(G=(V,E,w)\) adds Laplace noise to all edge weights and computes the shortest paths on this noisy graph. The output of the algorithm satisfies that the estimated distance between every pair is within an additive \(\pm O(n \log n/\varepsilon)\) of the actual distance (the absolute value of this parameter is called the accuracy of the algorithm). Moreover, this error is tight up to a logarithmic factor if the algorithm is required to release the shortest paths. The current paper shows you can privately release all the pairwise distances while suffering only a sublinear accuracy if you additionally release the edge weights (in place of releasing the shortest paths). In particular, this paper presents an \(\varepsilon\)-DP algorithm with sublinear \(\widetilde{O}(n^{2/3})\) accuracy.
Quantum algorithms for estimating quantum entropies by Youle Wang, Benchi Zhao, Xin Wang (arXiv) So, remember our post from December on sublinear quantum algorithms for estimation of quantum (von Neumann) entropy? The current paper begins by noting that the research so far (along the lines of the work above) assumes access to a quantum query model for the input state which we do not yet know how to construct efficiently. This paper addresses this issue and gives quantum algorithms to estimate the von Neumann entropy of a \(n\)-qubit quantum state \(\rho\) by using independent copies of the input state.
Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics by Yu Chen, Sanjeev Khanna, Zihan Tan (arXiv) As mentioned in the title, this paper studies sublinear algorithms for the metric MST and the metric TSP problem. The paper obtains a wide assortment of results and shows that both these problems admit an \(\alpha\)-approximation algorithm which uses \(O(n/\alpha)\) space. This algorithm assumes that the input is given as a stream of \(n \choose 2\) metric entries. Under this model, the paper also presents an \(\Omega(n/\alpha^2)\) space lower bound. Let me highlight one more result from the paper. In a previous news (from June 2020), we covered a result detailing a better than \(2\)-approximation for the graphic TSP and \((1,2)\) TSP which runs in sublinear time. This paper extends this result and obtains better than \(2\)-approximation for TSP on a relaively richer class of metrics.