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 :
Reports
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102240
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 10:40:31 AM
Last modification on : Sunday, April 28, 2019 - 1:23:07 AM

File

RR2006-05.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102240, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

11

Files downloads

30