Approximating the Determinant of Well-Conditioned Matrices by Shallow Circuits

Enric Boix-Adserà, Lior Eldar, Saeed Mehraban

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 [Ta…