A lean month by our (now high) standards. Three papers, on local computational algorithms for spanners, sublinear set cover, and quantum distribution testing.

Local Computation Algorithms for Spanners, by Merav Parter, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee (arXiv). Consider the problem of computing a \(k\)-spanner for a graph \(G\). This is a subgraph \(H\), where (for any pair of vertices) the shortest path distance in \(H\) is at most \(k\) times the corresponding distance in \(G\). A Local Computation Algorithm (LCA) essentially gives sublinear query access to (some spanner) \(H\), without any preprocessing on \(G\). In other words, an LCA takes as input an edge \((i,j)\) in \(G\), and in sublinear time says “yes” or “no”. Despite no preprocessing, it is guaranteed that all the “yes” answers form a spanner, and the number of “yes” answers is small. One of the main challenges in LCAs for graph problems is getting a polynomial dependence on \(\Delta\), the maximum degree. (Many results end up with an exponential dependence on \(\Delta\), essentially assuming bounded-degree.) This paper give an LCA outputting spanners of optimal size for \(k=3,5\), with query complexity \(n^{1-\alpha}\) (for constant \(\alpha\) depending on \(k\)). The second result works for general \(k\), but has a query complexity that is \(O(\Delta^4n^{2/3})\).

Set Cover in Sub-linear Time, by Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee (arXiv). Set cover needs no introduction. This paper considers sublinear algorithms for set cover. It is convenient to think of the instance as a binary \(m \times n\) matrix, for \(m\) sets over a universe of size \(n\). The query model gives access to the \(j\)th non-zero entry in a desired column/row. The aim is this paper is to actually construct a set cover, and not just approximate its size (the latter problem with initiated in Nguyen-Onak). The first result shows a black-box conversion of any set cover algorithm into a sublinear query complexity algorithm. Any \(\alpha\)-approximation for set cover can be converted into an \(O(\alpha)\)-approximation, that makes \(O(m(n/k)^{\beta} + nk)\) (where \(k\) is the optimal set cover size, and \(\beta < 1\) depends on \(\alpha\)). For large \(k\), the paper gives an \(O(mn/k)\) query, \(O(\log n)\)-approximation algorithm. There are various lower bounds given, that show these dependencies are necessary.

Distributional Property Testing in a Quantum World by András Gilyén and Tongyang Li (arXiv). There are two aspects to quantum distribution testing. First, we can think of faster distribution testing (for classical problems) using quantum computation. Second, we can generalize the problem of distribution testing to its quantum equivalent, called density operator testing (this papers gives the first result for this quantum generalization). A distribution is a non-negative vector in \(\mathbb{R}^n\) with unit \(l_1\)-norm. The quantum generalization, a density operator, is a PSD matrix in \(\mathbb{C}^n\) with unit trace. This paper has a number of results, along both aspects. For example, for the well-known problem of testing equality of distributions under total variation distance, the papers gives an \(\widetilde{O}(\sqrt{n}/\epsilon)\) tester (an improvement over classical lower bounds). For testing equality of density operators under the same distance, the paper gives an \(O(n/\epsilon)\) tester (note that the trivial bound is \(O(n^2)\), since the operator is a matrix).