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 = (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.
Type de document :
Pré-publication, Document de travail
13 pages. 2007
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00153736
Contributeur : Sylvain Perifel <>
Soumis le : lundi 11 juin 2007 - 16:37:43
Dernière modification le : mardi 24 avril 2018 - 13:52:55
Document(s) archivé(s) le : jeudi 8 avril 2010 - 19:36:53

Fichiers

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

Identifiants

  • HAL Id : ensl-00153736, version 1

Collections

Citation

Pierre Charbit, Emmanuel Jeandel, Pascal Koiran, Sylvain Perifel, Stéphan Thomassé. Finding a Vector Orthogonal to Roughly Half a Collection of Vectors. 13 pages. 2007. 〈ensl-00153736〉

Partager

Métriques

Consultations de la notice

164

Téléchargements de fichiers

81