Finding a vector orthogonal to roughly half a collection of vectors (Q2479315): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Pierre Charbit / rank | |||
Property / author | |||
Property / author: Steéphan Thomassé / rank | |||
Property / author | |||
Property / author: Pierre Charbit / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Steéphan Thomassé / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2161469686 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2784326 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4718423 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Very Fast Parallel Polynomial Arithmetic / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4542570 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2754200 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Topological complexity of the range searching / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4501520 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: VPSPACE and a transfer theorem over the reals / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Point location in arrangements of hyperplanes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Polynomial Linear Search Algorithm for the <i>n</i> -Dimensional Knapsack Problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The probabilistic method yields deterministic parallel algorithms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the topology of algorithms. I / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On decision trees for orthants / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4393484 / rank | |||
Normal rank |
Latest revision as of 20:10, 27 June 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