Vandermonde Matrices, NP-Completeness, (2002)
École Normale, Supérieure Lyon, Er Chistov, Hervé Fournier, Leonid Gurvits, Pascal Koiran, ...
Let K be an infinite field. We give polynomial time constructions of families of r-dimensional subspaces of K n with the following transversality property: any linear subspace of K n of dimension n...