# Finding a Vector Orthogonal to Roughly Half a Collection of Vectors

4 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Dimitri Grigoriev has shown that for any family of $N$ vectors in the $d$-dimensional linear space $E=(\ff{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-\sqrt{N}/2,N/2+\sqrt{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.
Document type :
Journal articles
Domain :

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00292703
Contributor : Stephan Thomasse <>
Submitted on : Wednesday, July 2, 2008 - 2:27:26 PM
Last modification on : Friday, March 27, 2020 - 2:56:39 AM
Long-term archiving on: : Friday, May 28, 2010 - 9:23:09 PM

### File

jc.pdf
Files produced by the author(s)

### Citation

Pierre Charbit, Emmanuel Jeandel, Pascal Koiran, Sylvain Perifel, Stéphan Thomassé. Finding a Vector Orthogonal to Roughly Half a Collection of Vectors. Journal of Complexity, Elsevier, 2008, 24, pp.39-53. ⟨10.1016/j.jco.2006.09.005⟩. ⟨lirmm-00292703⟩

Record views