The null space problem I. complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Data Encoding for Byzantine-Resilient Distributed Optimization (2019, background): “It is known that ﬁnding the sparsest basis for the null-space of a matrix is NP-hard [CP86].”
Most Tensor Problems Are NP-Hard (2009, background): “trix problems are tractable. For example, computing matrix (p;q)-norms when 1 qp1[Steinberg 2005], nonnegative rank of nonnegative matrices [Vavasis 2009; Arora et al. 2012], sparsest null vector [Coleman and Pothen 1986], and rank minimization with linear constraints [Natarajan 1995] are all known ”
Neurobiology of Aging: Contents (2005, unknown): “Moreover, even if a sparse null basis exists, the problem of computing a null basis Z (fundamental or not) with minimal number of nonzero entries has been shown to be NP-hard (Coleman and Pothen 1986, Pothen 1984).”
The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing (2012, background): “Even earlier, in [31], the authors claim to have a proof, but g ive credit to the dissertation [32] for establishing NP-hardness of spark computations.”
Data Encoding for Byzantine-Resilient Distributed Gradient Descent (2018, background): “It is known that finding the sparsest basis for the null-space of a matrix is NP-hard [24].”