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.
Type de document :
Article dans une revue
Journal of Complexity, Elsevier, 2008, 24, pp.39-53. 〈10.1016/j.jco.2006.09.005〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00292703
Contributeur : Stephan Thomasse <>
Soumis le : mercredi 2 juillet 2008 - 14:27:26
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : vendredi 28 mai 2010 - 21:23:09

Fichier

jc.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

473

Téléchargements de fichiers

154