Skip to Main content Skip to Navigation

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 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.
Document type :
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Colette Orange Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 10:40:31 AM
Last modification on : Saturday, September 11, 2021 - 3:19:15 AM


Files produced by the author(s)


  • HAL Id : hal-02102240, version 1



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⟩



Les métriques sont temporairement indisponibles