Finding a Vector Orthogonal to Roughly Half a Collection of Vectors

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.
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00292703
Contributor : Stephan Thomasse <>
Submitted on : Wednesday, July 2, 2008 - 2:27:26 PM
Last modification on : Thursday, February 7, 2019 - 4:50:36 PM
Long-term archiving on : Friday, May 28, 2010 - 9:23:09 PM

File

jc.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

694

Files downloads

241