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=(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 and we give an efficient, deterministic parallel algorithm which finds a vector achieving this bound. The optimality of the bound is also investigated.