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.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00153736
Contributor : Sylvain Perifel <>
Submitted on : Monday, June 11, 2007 - 4:37:43 PM
Last modification on : Friday, January 25, 2019 - 3:34:10 PM
Long-term archiving on : Thursday, April 8, 2010 - 7:36:53 PM

Files

vector.pdf
Files produced by the author(s)

Identifiers

  • 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. 2007. ⟨ensl-00153736⟩

Share

Metrics

Record views

210

Files downloads

183