E. Amaldi and V. Kann, The complexity and approximability of finding maximum feasible subsystems of linear relations, Theoretical Computer Science, vol.147, pp.181-210, 1995.

J. Cai, A. Naik, and D. Sivakumar, On the existence of hard sparse sets under weak reductions, Proc. STACS'96, vol.1046, pp.307-318, 1996.

R. Chandrasekaran, S. N. Kabadi, and K. Murty, Some NP-complete problems in linear programming, Operations Research Letters, vol.1, pp.101-103, 1982.

A. Chistov, Constructing a finite field within a polynomial time, Proc. 7th Soviet Conference on Mathematical Logic, 1984.

A. Chistov, Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic, Proc. 5th International FCT Conference, vol.199, pp.9-13, 1985.

M. Dyer, P. Gritzmann, and A. Hufnagel, On the complexity of computing mixed volumes, SIAM Journal on Computing, vol.27, issue.2, pp.356-400, 1998.

J. Erickson, New lower bounds for convex hull problems in odd dimensions, SIAM Journal on Computing, vol.28, issue.4, pp.1198-1214, 1999.

L. Khachiyan, On the complexity of approximating extremal determinants in matrices, Journal of Complexity, vol.11, pp.138-153, 1995.

P. Koiran, N. Portier, and G. Villard, A rank theorem for Vandermonde matrices, 2001.

S. Meiser, Point location in arrangements of hyperplanes. Information and Computation, vol.106, pp.286-303, 1993.

F. Meyer and H. Der, A polynomial linear search algorithm for the ndimensional knapsack problem, Journal of the ACM, vol.31, issue.3, pp.668-676, 1984.

F. Meyer and H. Der, Fast algorithms for n-dimensional restrictions of hard problems, Journal of the ACM, vol.35, issue.3, pp.740-747, 1988.

K. Mulmuley, A fast parallel algorithm to compute the rank of a matrix over an arbitrary field, Proc. 18th ACM Symposium on Theory of Computing, pp.338-339, 1986.

M. Roy and N. Vorobjov, The complexification and degree of a semi-algebraic set, Mathematische Zeitschrift, vol.239, issue.1, pp.131-142, 2002.

V. Shoup, New algorithms for finding irreducible polynomials over finite fields. Mathematics of Computation, vol.54, pp.435-447, 1990.