Approximating the Determinant of Well-Conditioned Matrices by Shallow Circuits

The determinant can be computed by classical circuits of depth $O(log^2 n)$, and therefore it can also be computed in classical space $O(log^2 n)$. Recent progress by Ta-Shma [Ta13] implies a method to approximate the determinant of Hermitian matrices with condition number $kappa$ in quantum space $O(log n + log kappa)$. However, it is not known how to perform the task in less than $O(log^2 n)$ space using classical resources only. In this work, we show that the condition number of a matrix implies an upper bound on the depth complexity (and therefore also on the space complexity) for this task: the determinant of Hermitian matrices with condition number $kappa$ can be approximated to inverse polynomial relative error with classical circuits of depth $tilde O(log n cdot log kappa)$, and in particular one can approximate the determinant for sufficiently well-conditioned matrices in depth $tilde{O}(log n)$. Our algorithm combines Barvinoks recent complex-analytic approach for approximating combinatorial counting problems [Bar16] with the Valiant-Berkowitz-Skyum-Rackoff depth-reduction theorem for low-degree arithmetic circuits [Val83].

Graph powering and spectral robustness

Spectral algorithms, such as principal component analysis and spectral clustering, typically require careful data transformations to be effective: upon observing a matrix $A$, one may look at the spectrum of $psi(A)$ for a properly chosen $psi$. The issue is that the spectrum of $A$ might be contaminated by non-informational top eigenvalues, e.g., due to scale` variations in the data, and the application of $psi$ aims to remove these. Designing a good functional $psi$ (and establishing what good means) is often challenging and model dependent. This paper proposes a simple and generic construction for sparse graphs, $$psi(A) = 1((I+A)^r ge1),$$ where $A$ denotes the adjacency matrix and $r$ is an integer (less than the graph diameter). This produces a graph connecting vertices from the original graph that are within distance $r$, and is referred to as graph powering. It is shown that graph powering regularizes the graph and decontaminates its spectrum in the following sense: (i) If the graph is drawn from the sparse ErdH{o}s-Renyi ensemble, which has no spectral gap, it is shown that graph powering produces a `maximal spectral gap, with the latter justified by establishing an Alon-Boppana result for powered graphs; (ii) If the graph is drawn from the sparse SBM, graph powering is shown to achieve the fundamental limit for weak recovery (the KS threshold) similarly to cite{massoulie-STOC}, settling an open problem therein. Further, graph powering is shown to be significantly more robust to tangles and cliques than previous spectral algorithms based on self-avoiding or nonbacktracking walk counts cite{massoulie-STOC,Mossel_SBM2,bordenave,colin3}. This is illustrated on a geometric block model that is dense in cliques.