Finding a vector orthogonal to roughly half a collection of vectors (Q2479315): Difference between revisions

It was shown by \textit{D. Grigoriev} [J. Complexity 16, No. 1, 50--53 (2000; Zbl 0951.68024)] 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. The authors show that the range \([N/3,2N/3] \) can be replaced by the much smaller range \([ N/2-\sqrt{N} /2,N/2+\sqrt{N}/2] \) and give an efficient deterministic parallel algorithm which finds a vector achieving this bound. The optimality of the bound is also investigated.