Finding a vector orthogonal to roughly half a collection of vectors

Abstract: Dimitri Grigoriev has shown that for any family of N vectors in the d-dimensional linear space , there exists a vector in E which is orthogonal to at least and at most vectors of the family. We show that the range can be replaced by the much smaller range and we give an efficient, deterministic parallel algorithm which finds a vector achieving this bound. The optimality of the bound is also investigated. [Copyright &y& Elsevier]