Title: "Polynomial inequalities over a quadratic map with
low-dimensional image are easy".
D.V. Pasechnik (Univ. Frankfurt, Germany),
jointly with E. de Klerk (TU Delft, NL) and D. Grigoriev (IRMAR, Univ.
Rennes I, France)
 
Let
p_i(Y)>=0 (0<i<s+1),
p_i(Y) =0 (s<i<s')
be a system of polynomial
inequalities and equations in Y=(Y_1,...,Y_k), and Q:R^n->R^k a
quadratic map, that is, a vector of k quadratic polynomials in n
variables.
Then the problem of finding an exact solution of the system
p_i(Q(X))>=0 (0<i<s+1),
p_i(Q(X)) =0 (s<i<s'),
as well as linear optimization subject to such a set of constraints,
is solvable within (sdn)^O(k) arthmetic operations, where d is
the maximal degree of the p_i's.
 
Morever, we find, within the same operation count, the range of
a linear function over such set.
 
One interesting and immediate corollary is the best known bound on the
complexity of semidefinite programming claimed without a proof by
Khachiyan and Porkolab in 1997.