Last month saw seven papers covering a reasonable range of topics in property testing. Our line up contains diversions in distribution testing, graph property testing and quantum. Let us start with a result from the quantum land on spectrum estimation. (And oh, let me add that all em-dashes in this post are human generated).
Spectrum Estimation is Almost as Hard as Tomography by Marco Fanizza, Ryan O’Donnell, Chirag Wadhwa (arXiv) A \(d\)-dimensional quantum state is modeled as a density matrix (i.e., a complex-valued PSD matrix with unit trace). Take a quantum state \(\boldsymbol{\rho} \in \mathbb{C}^{d \times d}\) and let \(spec(\boldsymbol{\rho})\) denote the collection of all eigenvalues of this state (also referred to as the spectrum of \(\boldsymbol{\rho}\)). The paper considers the computational challenge of estimating the spectrum of an unknown quantum state \(\boldsymbol{\rho}\). The algorithm is required to return a vector \(\widehat{\boldsymbol{\alpha}}\) which is within a small total variation distance \(\varepsilon\) of the spectrum of \(\boldsymbol{\rho}\). The main result establishes a lower bound: you cannot meet this challenge with fewer than \(\Omega(d^{2-\varepsilon})\) copies of \(\boldsymbol{\rho}\). This also shows that the recent work of Pelecanos-Spilecki-Tang-Wright achieves near-optimal dimension dependence for this task.
Testing Distributions Against Bounded Distinguishers by Mark Bun, Rathin Desai, Renato Ferreira Pinto Jr (arXiv) Alright, so let us go back to the recurring theme of testing properties of high-dimensional distributions. So, in your hand sits a distribution supported on \(\{0,1\}^n\). Classic tasks like identity testing with respect to a fixed reference distribution can now be seen to have very large sample complexity. To allay this, a lot of previous works take the BWCA approach and instead develop testers in situations where the reference distribution is structured. Other approaches proceed by assuming access to stronger sampling oracles. The featured paper considers a different twist. Let \(\boldsymbol{p}\) denote the input distribution and we want to test whether \(\boldsymbol{p} = \boldsymbol{p}_{REF}\). We are promised that either \(\boldsymbol{p} = \boldsymbol{p}_{REF}\), or it satisfies \(dist_{\mathcal{F}}(\boldsymbol{p}, \boldsymbol{p}_{REF}) \geq \varepsilon\) (where \(\mathcal{F}\) is a collection of boolean tests). Recall that the familiar notion of total variation distance \(dist_{TV}(\boldsymbol{p}, \boldsymbol{q})\) is obtained by letting \(\mathcal{F}\) range over the family of all boolean tests. In situations where \(\mathcal{F}\) is a special subclass of all boolean tests, we get an interesting notion of total variation distance according to the suite of tests in the class \(\mathcal{F}\). The paper goes on to derive a bunch of interesting results in this framework. For illustration, here is an example result from the paper: suppose you know the Rademacher complexity of the reference distribution with respect to the subclass \(\mathcal{F}\) is small. Theorem 1.3 in the paper proves that this means the sample complexity of identity testing (with respect to \(\boldsymbol{p}_{REF}\)) under the “\(\mathcal{F}\)”-distance is also small.
Testing the Independent Set Property in Hypergraphs by Elena Grigorescu, Shreya Nasa, Cameron Seth (arXiv) For this paper, I will let a paraphrasing of the abstract do the talking.
Alright, so here is another property testing problem, this time for hypergraphs. Consider a \(q\)-uniform hypergraph on \(n\) vertices, and suppose we want to test whether it contains an independent set of size \(\rho n\), or is \(\varepsilon\)-far from having such an independent set. The paper proves a new upper bound of \(\widetilde{O}\left(\frac{q\rho^{2q-3}}{\varepsilon^2((q-2)!)^2}\right)\) on the sample complexity of this problem. This achieves the optimal dependence on \(\varepsilon\) and gives an exponential improvement in the dependence on \(q\) over the previous best bound. The proof uses a new application of the hypergraph container method.
Graph k-Coloring in Average Sublinear Time by Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, Shlomo Tauber (arXiv) Here is (yet another!) interesting problem that I did not know about. Consider the setting where you have query access to adjacency matrix of an input graph and for a fixed \(k > 2\), let us take a \(k\)-colorable graph and let us consider the task of coloring a random \(k\)-colorable graph on \(n\) vertices. Dyer and Frieze presented algorithms for this task which have an average running time of \(O(n^2)\) over this ensemble. The featured paper presents algorithms which have a running time of \(O(nk)\) over this ensemble (as long as \(k \leq n^{c_0}\)). Quoting from the paper
A key new ingredient and conceptual contribution is a method for certifying that a small random
subgraph is uniquely colorable, meaning the coloring is unique up to permuting the color classes.
The paper notes that their algorithms also yield a LCA which can be used for \(k\)-coloring that works well over our \(k\)-colorable ensemble. I will leave out the detailed input/output specification of the LCA, rest assured it is worth your time (in my view at least).
Optimal Stabilizer Testing and Learning with Limited Quantum Memory by Srinivasan Arunachalam, Louis Schatzki (arXiv) Here is a quantum property testing problem that I found particularly interesting, although I will admit that I am way out of my depth when it comes to the technical details. Suppose you are given copies of an unknown \(n\)-qubit state, and you want to test whether it is a stabilizer state. The catch is that you are only allowed to keep \(k\) qubits in coherent quantum memory between measurements.
With unrestricted memory, stabilizer states can be tested using just 6 copies, whereas learning an \(n\)-qubit stabilizer state requires \(\Theta(n)\) copies. The paper shows that this striking gap disappears under memory constraints: testing requires \(\Theta(n-k)\) copies, while learning requires \(\Theta(n^2/k)\) copies (for non-adaptive learners). In particular, even with \(0.99n\) qubits of coherent memory, testing still requires \(\Theta(n)\) copies.
The paper thus identifies coherent quantum memory as the resource responsible for the dramatic separation between testing and learning in this setting. I will leave the technical details to the quantum folks!
Testing Unate Distributions by Daeho Lee, Shivam Nadimpalli, Mingda Qiao, Ronitt Rubinfeld (arXiv) Again, let us consider the task of testing properties of high-dimensional distributions. A distribution \(\mathcal{D}\) supported on the Boolean hypercube \(\{+1,-1\}^n\) is unate if there exists \(\sigma \in \{+1,-1\}^n\) such that \(\mathcal{D}(x \oplus \sigma)\) is a monotone probability distribution. Recall that a probability distribution \(\mathcal{P}\) over the hypercube is monotone if \(\mathcal{P}(x) \leq \mathcal{P}(y)\) whenever \(x\) precedes \(y\) according to the partial order on the hypercube.
Assuming that the input distribution is unate, the paper presents uniformity testers with sample complexity \(\widetilde{O}(n^{3/2}/\varepsilon^2)\). The paper also presents a matching lower bound. Additionally, the paper presents algorithms for testing whether an input distribution is unate assuming access to the subcube conditional model.
New Complexity Classes in Locally Checkable Labeling for Local Computation Algorithms by Sijin Peng (arXiv) One rich direction in the sublinear algorithms literature deals with LCAs. Attempting a complexity classification of LCAs, the paper asks whether, for some function \(f(n) \gg \Omega(\log n)\) of our choice, we could hack up some algorithmic objective for which we can design LCAs with complexity \(\widetilde{O}(f(n))\). One of the main results of the paper asserts that, for every positive integer \(k\), you can hack up an LCL problem whose LCA complexity is \(\Theta(\log^k n)\). The rich class here refers to Locally Checkable Labeling Problems on bounded-degree graphs. These results are also proved in the VOLUME model—which I will not detail here. For more details, refer to the paper.