Finding a vector orthogonal to roughly half a collection of vectors - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2006

Finding a vector orthogonal to roughly half a collection of vectors

(1) , (1) , (1) , (1) , (1)
1

Résumé

Dimitri Grigoriev has shown that for any family of N vectors in the ddimensionallinear space E = (F2)d, there exists a vector in E which isorthogonal to at least N/3 and at most 2N/3 vectors of the family. Weshow that the range [N/3, 2N/3] can be replaced by the much smaller range[N/2 − √N/2,N/2 + √N/2] and we give an efficient, deterministic parallelalgorithm which finds a vector achieving this bound. The optimality of thebound is also investigated.
Dimitri Grigoriev a montré que pour toute famille de N vecteurs de l’espace vectoriel E = (F2)d de dimension d sur le corps à deux éléments, il existe un vecteur de E orthogonal à au moins N/3 et au plus 2N/3 vecteursde la famille. Nous montrons que l’intervalle [N/3, 2N/3] peut être réduit à[N/2 − √N/2,N/2+ √N/2], étudions l’optimalité de cette borne, et donnons un algorithme parallèle déterministe efficace pour trouver un vecteur dans cet intervalle.
Fichier principal
Vignette du fichier
RR2006-05.pdf (232.62 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02102240 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02102240 , version 1

Citer

Pierre Charbit, Emmanuel Jeandel, Pascal Koiran, Sylvain Perifel, Stefan Thomasse. Finding a vector orthogonal to roughly half a collection of vectors. [Research Report] LIP RR-2006-05, Laboratoire de l'informatique du parallélisme. 2006, 2+11p. ⟨hal-02102240⟩
10 Consultations
97 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More