Finding a Vector Orthogonal to Roughly Half a Collection of Vectors - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Journal of Complexity Year : 2008

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.
Fichier principal
Vignette du fichier
jc.pdf (255.04 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-00292703 , version 1 (02-07-2008)

Identifiers

Cite

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, 2008, 24, pp.39-53. ⟨10.1016/j.jco.2006.09.005⟩. ⟨lirmm-00292703⟩
393 View
212 Download

Altmetric

Share

Gmail Facebook X LinkedIn More