On Projections of Semi-Algebraic Sets Defined by Few Quadratic Inequalities

Let S⊂ℝ ^k+m be a compact semi-algebraic set defined by P ₁≥0,…,P _ℓ ≥0, where P _i ∈ℝX ₁,…,X _k ,Y ₁,…,Y _m ], and deg (P _i )≤2, 1≤i≤ℓ. Let π denote the standard projection from ℝ ^k+m onto ℝ ^m . We prove that for any q>0, the sum of the first q Betti numbers of π(S) is bounded by (k+m) ^{O(q ℓ)}. We also present an algorithm for computing the first q Betti numbers of π(S), whose complexity is . For fixed q and ℓ, both the bounds are polynomial in k+m. The author was supported in part by an NSF Career Award 0133597 and a Sloan Foundation Fellowship.