Finding a vector orthogonal to roughly half a collection of vectors
Dimitri Grigoriev has shown that for any family of N vectors in the d-dimensional linear space E = (F-2)(d), there exists a vector in E which is orthogonal to at least N/3 and at most 2N/3 vectors of the family. We show that the range [N/3, 2N/3] can be replaced by the much smaller range [N/2 - root N/2, N/2 + root N/2] and we give an efficient, deterministic parallel algorithm which finds a vector achieving this bound. The optimality of the bound is also investigated. (c) 2007 Elsevier Inc. All rights reserved.
parallel algorithms algebraic complexity decision trees derandomization