HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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 metadata

Cited literature [17 references]  Display  Hide  Download

Contributor : Sylvain Perifel Connect in order to contact the contributor
Submitted on : Monday, June 11, 2007 - 4:37:43 PM
Last modification on : Saturday, September 11, 2021 - 3:17:23 AM
Long-term archiving on: : Thursday, April 8, 2010 - 7:36:53 PM


Files produced by the author(s)


  • HAL Id : ensl-00153736, version 1



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⟩



Record views


Files downloads