Finding a Vector Orthogonal to Roughly Half a Collection of Vectors - ENS de Lyon - École normale supérieure de Lyon Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2007

Finding a Vector Orthogonal to Roughly Half a Collection of Vectors

Résumé

Dimitri Grigoriev has shown that for any family of N vectors in the d-dimensional linear space E = (F_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 − √N /2, N/2 + √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
vector.pdf (218.14 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

ensl-00153736 , version 1 (11-06-2007)

Identifiants

  • HAL Id : ensl-00153736 , version 1

Citer

Pierre Charbit, Emmanuel Jeandel, Pascal Koiran, Sylvain Perifel, Stéphan Thomassé. Finding a Vector Orthogonal to Roughly Half a Collection of Vectors. 2007. ⟨ensl-00153736⟩
129 Consultations
165 Téléchargements

Partager

Gmail Facebook X LinkedIn More