Finding a vector orthogonal to roughly half a collection of vectors (Q2479315): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
Property / author | |||
Property / author: Pierre Charbit / rank | |||
Property / author | |||
Property / author: Steéphan Thomassé / rank | |||
Revision as of 13:43, 15 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Finding a vector orthogonal to roughly half a collection of vectors |
scientific article |
Statements
Finding a vector orthogonal to roughly half a collection of vectors (English)
0 references
26 March 2008
0 references
It was shown by \textit{D. Grigoriev} [J. Complexity 16, No. 1, 50--53 (2000; Zbl 0951.68024)] 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. The authors show that the range \([N/3,2N/3] \) can be replaced by the much smaller range \([ N/2-\sqrt{N} /2,N/2+\sqrt{N}/2] \) and give an efficient deterministic parallel algorithm which finds a vector achieving this bound. The optimality of the bound is also investigated.
0 references
algebraic complexity
0 references
decision trees
0 references
parallel algorithms
0 references
derandomization
0 references
orthogonalization
0 references