Finding a vector orthogonal to roughly half a collection of vectors

AbstractDimitri Grigoriev has shown that for any family of N vectors in the d-dimensional linear space E=(F2)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-N/2,N/2+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