zbMATH — the first resource for mathematics

Finding a vector orthogonal to roughly half a collection of vectors. (English) Zbl 1140.65033
It was shown by 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.

65F30 Other matrix algorithms (MSC2010)
65Y05 Parallel numerical computation
65F25 Orthogonalization in numerical linear algebra
65Y20 Complexity and performance of numerical algorithms
Full Text: DOI
[1] Alon, N.; Spencer, J., The probabilistic method, (2000), Wiley Interscience Series in Discrete Mathematics and Optimization, Wiley New York
[2] Clote, P.; Kranakis, E., Boolean functions and computation models, texts in theoretical computer science (an EATCS series), (2002), Springer Berlin
[3] Eberly, W., Very fast parallel polynomial arithmetic, SIAM J. comput., 18, 5, 955-976, (1989) · Zbl 0694.68029
[4] H. Fournier, P. Koiran, Are lower bounds easier over the reals?, in: Proceedings of the 30th ACM Symposium on Theory of Computing, 1998, pp. 507-513. · Zbl 1028.68051
[5] Fournier, H.; Koiran, P., Lower bounds are not easier over the reals: inside PH, (), 832-843 · Zbl 0973.68081
[6] Grigoriev, D., Topological complexity of the range searching, J. complexity, 16, 50-53, (2000) · Zbl 0951.68024
[7] Koiran, P., Circuits versus trees in algebraic complexity, (), 35-52 · Zbl 0959.68045
[8] P. Koiran, S. Perifel, VPSPACE and a transfer theorem over the reals, in: Proceedings of STACS 2007, LNCS 4393, 2007, pp. 417-428. A longer version is available from \(\langle\)http://prunel.ccsd.cnrs.fr/ensl-00103018⟩. · Zbl 1146.68379
[9] Meiser, S., Point location in arrangements of hyperplanes, Inf. comput., 106, 2, 286-303, (1993) · Zbl 0781.68121
[10] Meyer auf der Heide, F., A polynomial linear search algorithm for the \(n\)-dimensional knapsack problem, J. ACM, 31, 3, 668-676, (1984) · Zbl 0631.68037
[11] Meyer auf der Heide, F., Fast algorithms for \(n\)-dimensional restrictions of hard problems, J. ACM, 35, 3, 740-747, (1988)
[12] Motwani, R.; Naor, J.; Naor, M., The probabilistic method yields deterministic parallel algorithms, J. comput. syst. sci., 49, 478-516, (1994) · Zbl 0824.68047
[13] Riordan, J., Combinatorial identities, (1979), Wiley New York
[14] Smale, S., On the topology of algorithms. I, J. complexity, 3, 81-89, (1987) · Zbl 0639.68042
[15] R. Sprugnoli, Combinatorial Identities, Technical report, Università di Firenze, 2004.
[16] Vassiliev, V.A., On decision trees for orthants, Inf. process. lett., 62, 5, 265-268, (1997) · Zbl 1337.68138
[17] H. Vollmer, Introduction to Circuit Complexity: a Uniform Approach, Texts in Theoretical Computer Science (an EATCS Series), Springer, Berlin, 1999. · Zbl 0931.68055
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.