Finding a vector orthogonal to roughly half a collection of vectors

Pierre Charbit (1) , Emmanuel Jeandel (1) , Pascal Koiran (1) , Sylvain Perifel (1) , Stefan Thomasse (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

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.

Dimitri Grigoriev a montré que pour toute famille de N vecteurs de l’espace vectoriel E = (F2)d de dimension d sur le corps à deux éléments, il existe un vecteur de E orthogonal à au moins N/3 et au plus 2N/3 vecteursde la famille. Nous montrons que l’intervalle [N/3, 2N/3] peut être réduit à[N/2 − √N/2,N/2+ √N/2], étudions l’optimalité de cette borne, et donnons un algorithme parallèle déterministe efficace pour trouver un vecteur dans cet intervalle.

Mots clés: Algebraic complexity; Decision trees; Parallel algorithms; Dérandomization

Mots clés: Algorithmes parallèles; Arbres de décision; Complexité algébrique

Domaines: Informatique [cs]

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⟩