ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY
---
paper_title: Algorithms in Real Algebraic Geometry

paper_content:

Algebraically Closed Fields.- Real Closed Fields.- Semi-Algebraic Sets.- Algebra.- Decomposition of Semi-Algebraic Sets.- Elements of Topology.- Quantitative Semi-algebraic Geometry.- Complexity of Basic Algorithms.- Cauchy Index and Applications.- Real Roots.- Cylindrical Decomposition Algorithm.- Polynomial System Solving.- Existential Theory of the Reals.- Quantifier Elimination.- Computing Roadmaps and Connected Components of Algebraic Sets.- Computing Roadmaps and Connected Components of Semi-algebraic Sets.
---
paper_title: Algorithms in Real Algebraic Geometry

paper_content:

Algebraically Closed Fields.- Real Closed Fields.- Semi-Algebraic Sets.- Algebra.- Decomposition of Semi-Algebraic Sets.- Elements of Topology.- Quantitative Semi-algebraic Geometry.- Complexity of Basic Algorithms.- Cauchy Index and Applications.- Real Roots.- Cylindrical Decomposition Algorithm.- Polynomial System Solving.- Existential Theory of the Reals.- Quantifier Elimination.- Computing Roadmaps and Connected Components of Algebraic Sets.- Computing Roadmaps and Connected Components of Semi-algebraic Sets.
---
paper_title: Triangulation of semi-analytic sets

paper_content:

A centrifugal pump for use in pumping hot liquids under pressure. A rotatable shaft, having an impeller at its lower end, is positioned along the axis of a generally cylindrical pump casing. The pump casing has a suction nozzle at its lower end, and a discharge nozzle near the upper end. A cylindrical outer shell surrounds the shaft within the casing, and a flange on the outer shell is secured to the top of the casing. A cylindrical inner shell is positioned inside the outer shell, surrounding the shaft, and a space is formed between the inner shell and the outer shell. The space provides an effective thermal barrier to protect the shaft. A bearing assembly for the shaft is secured to the inner shell, and a cooler is positioned between the bearing assembly and the impeller, thereby protecting the bearing assembly from the heat of the fluid being circulated by the pump. Seals are inserted within the inner shell above the bearing assembly, and these seals confine the high-pressure liquid within the pump.
---
paper_title: Algorithms in Real Algebraic Geometry

paper_content:

Algebraically Closed Fields.- Real Closed Fields.- Semi-Algebraic Sets.- Algebra.- Decomposition of Semi-Algebraic Sets.- Elements of Topology.- Quantitative Semi-algebraic Geometry.- Complexity of Basic Algorithms.- Cauchy Index and Applications.- Real Roots.- Cylindrical Decomposition Algorithm.- Polynomial System Solving.- Existential Theory of the Reals.- Quantifier Elimination.- Computing Roadmaps and Connected Components of Algebraic Sets.- Computing Roadmaps and Connected Components of Semi-algebraic Sets.
---
paper_title: Quantifier elimination for real closed fields by cylindrical algebraic decomposition

paper_content:

Tarski in 1948, (Tarski 1951) published a quantifier elimination method for the elementary theory of real closed fields (which he had discovered in 1930). As noted by Tarski, any quantifier elimination method for this theory also provides a decision method, which enables one to decide whether any sentence of the theory is true or false. Since many important and difficult mathematical problems can be expressed in this theory, any computationally feasible quantifier elimination algorithm would be of utmost significance.
---
paper_title: A Decision Method for Elementary Algebra and Geometry

paper_content:

By a decision method for a class K of sentence (or other expressions) is meant a method by means of which, given any sentence θ, one can always decide in a finite number of steps whether θ is in K; by a decision problem for a class K we mean the problem of finding a decision method for K. A decision method must be like a recipe, which tells one what to do at each steps so that no intelligence is required to follow it; and the method can be applied by anyone so long as he is able to read and follow directions.
---
paper_title: Polar varieties, real equation solving, and data structures: the hypersurface case

paper_content:

In this paper we apply for the first time a new method for multivariate equation solving which was developed in \cite{gh1}, \cite{gh2}, \cite{gh3} for complex root determination to the {\em real} case. Our main result concerns the problem of finding at least one representative point for each connected component of a real compact and smooth hypersurface. The basic algorithm of \cite{gh1}, \cite{gh2}, \cite{gh3} yields a new method for symbolically solving zero-dimensional polynomial equation systems over the complex numbers. One feature of central importance of this algorithm is the use of a problem--adapted data type represented by the data structures arithmetic network and straight-line program (arithmetic circuit). The algorithm finds the complex solutions of any affine zero-dimensional equation system in non-uniform sequential time that is {\em polynomial} in the length of the input (given in straight--line program representation) and an adequately defined {\em geometric degree of the equation system}. Replacing the notion of geometric degree of the given polynomial equation system by a suitably defined {\em real (or complex) degree} of certain polar varieties associated to the input equation of the real hypersurface under consideration, we are able to find for each connected component of the hypersurface a representative point (this point will be given in a suitable encoding). The input equation is supposed to be given by a straight-line program and the (sequential time) complexity of the algorithm is polynomial in the input length and the degree of the polar varieties mentioned above.
---
paper_title: Algorithms in Real Algebraic Geometry

paper_content:

Algebraically Closed Fields.- Real Closed Fields.- Semi-Algebraic Sets.- Algebra.- Decomposition of Semi-Algebraic Sets.- Elements of Topology.- Quantitative Semi-algebraic Geometry.- Complexity of Basic Algorithms.- Cauchy Index and Applications.- Real Roots.- Cylindrical Decomposition Algorithm.- Polynomial System Solving.- Existential Theory of the Reals.- Quantifier Elimination.- Computing Roadmaps and Connected Components of Algebraic Sets.- Computing Roadmaps and Connected Components of Semi-algebraic Sets.
---
paper_title: Quantifier elimination for real closed fields by cylindrical algebraic decomposition

paper_content:

Tarski in 1948, (Tarski 1951) published a quantifier elimination method for the elementary theory of real closed fields (which he had discovered in 1930). As noted by Tarski, any quantifier elimination method for this theory also provides a decision method, which enables one to decide whether any sentence of the theory is true or false. Since many important and difficult mathematical problems can be expressed in this theory, any computationally feasible quantifier elimination algorithm would be of utmost significance.
---
paper_title: Semi-monotone sets

paper_content:

A coordinate cone in R^n is an intersection of some coordinate hyperplanes and open coordinate half-spaces. A semi-monotone set is a defnable in an o-minimal structure over the reals, open bounded subset of R^n such that its intersection with any translation of any coordinate cone is connected. This can be viewed as a generalization of the convexity property. Semi-monotone sets have a number of interesting geometric and combinatorial properties. The main result of the paper is that every semi-monotone set is a topological regular cell.
---
paper_title: Real quantifier elimination is doubly exponential

paper_content:

We show that quantifier elimination over real closed fields can require doubly exponential space (and hence time). This is done by explicitly constructing a sequence of expressions whose length is linear in the number of quantifiers, but whose quantifier-free expression has length doubly exponential in the number of quantifiers. The results can be applied to cylindrical algebraic decomposition, showing that this can be doubly exponential. The double exponents of our lower bounds are about one fifth of the double exponents of the best-known upper bounds.
---
paper_title: On the combinatorial and algebraic complexity of quantifier elimination

paper_content:

In this paper, a new algorithm for performing quantifier elimination from first order formulas over real closed fields in given. This algorithm improves the complexity of the asymptotically fastest algorithm for this problem, known to this data. A new feature of this algorithm is that the role of the algebraic part (the dependence on the degrees of the imput polynomials) and the combinatorial part (the dependence on the number of polynomials) are sparated. Another new feature is that the degrees of the polynomials in the equivalent quantifier-free formula that is output, are independent of the number of input polynomials. As special cases of this algorithm new and improved algorithms for deciding a sentence in the first order theory over real closed fields, and also for solving the existential problem in the first order theory over real closed fields, are obtained.
---
paper_title: Counting connected components of a semialgebraic set in subexponential time

paper_content:

Let a semialgebraic set be defined by a quantifier-free formula with atomic subformulas of the form fi>0, 0,1 ≦ i ≦ where the polynomials fieℤ[X1,..., Xn] of degree deg (fi)<d have absolute value of the coefficients at most 2M. An algorithm is constructed which finds the connected components of the semialgebraic set (i.e., giving formulas for them) in a time that is polynomial inM (kd)ro(1). Collins' previously known method has a bound which is polynomial inM (kd)ro(1).
---
paper_title: Algorithms in Real Algebraic Geometry

paper_content:

Algebraically Closed Fields.- Real Closed Fields.- Semi-Algebraic Sets.- Algebra.- Decomposition of Semi-Algebraic Sets.- Elements of Topology.- Quantitative Semi-algebraic Geometry.- Complexity of Basic Algorithms.- Cauchy Index and Applications.- Real Roots.- Cylindrical Decomposition Algorithm.- Polynomial System Solving.- Existential Theory of the Reals.- Quantifier Elimination.- Computing Roadmaps and Connected Components of Algebraic Sets.- Computing Roadmaps and Connected Components of Semi-algebraic Sets.
---
paper_title: Description of the Connected Components of a Semialgebraic in Single Exponential Time

paper_content:

This paper is devoted to the following result: letR be a real closed field and letS be a semialgebraic subset ofRn defined by a boolean combination of polynomial inequalities. LetD be the sum of the degrees of the polynomials involved. Then it is possible to find algorithmically a description of the semialgebraically connected components ofS in sequential timeDno(1) and parallel time (n logD)o(1) This implies that the problem of finding the connected components of a semialgebraic set can be solved in P-SPACE.
---
paper_title: Solving Systems of Polynomial Inequalities in Subexponential Time

paper_content:

A sweep auger radially mounted within a storage bin is rotatable horizontally across the bin floor about a vertical axis located centrally of the bin. An upright distributing auger arranged coaxially with the vertical axis has its lower end adjacent the inner end of the sweep auger and its upper end spaced from the roof of the bin. The sweep auger is of a construction such that for each complete revolution across the bin floor it moves predetermined volumes of material over given axial sections thereof for delivery to the distributing auger. The material or grain discharged from the distributing auger is spread across the top surface of the grain stored in the bin. All of the grain in the bin is thus acted upon continuously for circulation through the bin for drying purposes. Field grain may be introduced through the roof of the bin for concurrent distribution and circulation with the grain already in the bin. A bin unloading auger is located below the bin floor to receive grain directly from the sweep auger for discharge exteriorly of the bin.
---
paper_title: Algorithms in Real Algebraic Geometry

paper_content:

Algebraically Closed Fields.- Real Closed Fields.- Semi-Algebraic Sets.- Algebra.- Decomposition of Semi-Algebraic Sets.- Elements of Topology.- Quantitative Semi-algebraic Geometry.- Complexity of Basic Algorithms.- Cauchy Index and Applications.- Real Roots.- Cylindrical Decomposition Algorithm.- Polynomial System Solving.- Existential Theory of the Reals.- Quantifier Elimination.- Computing Roadmaps and Connected Components of Algebraic Sets.- Computing Roadmaps and Connected Components of Semi-algebraic Sets.
---
paper_title: On Computing a Set of Points Meeting Every Cell Defined by a Family of Polynomials on a Variety

paper_content:

We consider a family ofspolynomials, P = {P1, ?,Ps}, inkvariables with coefficients in a real closed fieldR, each of degree at mostd, and an algebraic varietyVof real dimensionk? which is defined as the zero set of a polynomialQof degree at mostd. The number of semi-algebraically connected components of all non-empty sign conditions on P overVis bounded bysk?(O(d))k. In this paper we present a new algorithm to compute a set of points meeting every semi-algebraically connected component of each non-empty sign condition of P overV. Its complexity issk? + 1dO(k). This interpolates a sequence of results between the Ben-Or?Kozen?Reif algorithm which is the casek? = 0, in one variable, and the Basu?Pollack?Roy algorithm which is the casek? =k. It improves the results where the same problem was solved in timesk? + 1dO(k?k).
---
paper_title: Algorithms in Real Algebraic Geometry

paper_content:

Algebraically Closed Fields.- Real Closed Fields.- Semi-Algebraic Sets.- Algebra.- Decomposition of Semi-Algebraic Sets.- Elements of Topology.- Quantitative Semi-algebraic Geometry.- Complexity of Basic Algorithms.- Cauchy Index and Applications.- Real Roots.- Cylindrical Decomposition Algorithm.- Polynomial System Solving.- Existential Theory of the Reals.- Quantifier Elimination.- Computing Roadmaps and Connected Components of Algebraic Sets.- Computing Roadmaps and Connected Components of Semi-algebraic Sets.
---
paper_title: Certificates of Positivity in the Bernstein Basis

paper_content:

Let $P\in\mathbb{Z[X]}$ be a polynomial of degree p with coefficients in the monomial basis of bit-size bounded by τ. If P is positive on [−1,1], we obtain a certificate of positivity (i.e., a description of P making obvious that it is positive) of bit-size O(p 4(τ+log 2 p)). Previous comparable results had a bit-size complexity exponential in p and τ (Powers and Reznick in Trans. Am. Math. Soc. 352(10):4677–4692, 2000; Powers and Reznick in J. Pure Appl. Algebra 164:221–229, 2001).
---
paper_title: Algorithms in Real Algebraic Geometry

paper_content:

Algebraically Closed Fields.- Real Closed Fields.- Semi-Algebraic Sets.- Algebra.- Decomposition of Semi-Algebraic Sets.- Elements of Topology.- Quantitative Semi-algebraic Geometry.- Complexity of Basic Algorithms.- Cauchy Index and Applications.- Real Roots.- Cylindrical Decomposition Algorithm.- Polynomial System Solving.- Existential Theory of the Reals.- Quantifier Elimination.- Computing Roadmaps and Connected Components of Algebraic Sets.- Computing Roadmaps and Connected Components of Semi-algebraic Sets.
---
paper_title: Linear Solving for Sign Determination

paper_content:

We give a specific method to solve with quadratic complexity the linear systems arising in known algorithms to deal with the sign determination problem. In particular, this enable us to improve the complexity bound for sign determination in the univariate case.
---
paper_title: Bounding the radii of balls meeting every connected component of semi-algebraic sets

paper_content:

We prove explicit bounds on the radius of a ball centered at the origin which is guaranteed to contain all bounded connected components of a semi-algebraic set $S \subset \mathbbm{R}^k$ defined by a quantifier-free formula involving $s$ polynomials in $\mathbbm{Z}[X_1, ..., X_k]$ having degrees at most $d$, and whose coefficients have bitsizes at most $\tau$. Our bound is an explicit function of $s, d, k$ and $\tau$, and does not contain any undetermined constants. We also prove a similar bound on the radius of a ball guaranteed to intersect every connected component of $S$ (including the unbounded components). While asymptotic bounds of the form $2^{\tau d^{O (k)}}$ on these quantities were known before, some applications require bounds which are explicit and which hold for all values of $s, d, k$ and $\tau$. The bounds proved in this paper are of this nature.
---
paper_title: The complexity of elementary algebra and geometry

paper_content:

A tamper-evident top closure lid construction for a container. The lid is integrally formed from a plastic cover member, the member carrying a main and a secondary paperboard insert on its upper surface, the member and insert being bonded together. The plastic cover member has an integral tongue to define, upon tongue pivoting, an opening in the member. The main paperboard insert is hinged about a contiguous pivot axis. The secondary insert carries a pull tab. If formed from a brittle plastics material, pulling the pull tab breaks the plastics member at its tongue hinge. The pull tab is so formed as to indicate tampering to a prospective purchaser of the container provided with the top closure lid construction of this invention. The lid may also be provided with an upstanding rim to facilitate stacking.
---
paper_title: Solving Systems of Polynomial Inequalities in Subexponential Time

paper_content:

A sweep auger radially mounted within a storage bin is rotatable horizontally across the bin floor about a vertical axis located centrally of the bin. An upright distributing auger arranged coaxially with the vertical axis has its lower end adjacent the inner end of the sweep auger and its upper end spaced from the roof of the bin. The sweep auger is of a construction such that for each complete revolution across the bin floor it moves predetermined volumes of material over given axial sections thereof for delivery to the distributing auger. The material or grain discharged from the distributing auger is spread across the top surface of the grain stored in the bin. All of the grain in the bin is thus acted upon continuously for circulation through the bin for drying purposes. Field grain may be introduced through the roof of the bin for concurrent distribution and circulation with the grain already in the bin. A bin unloading auger is located below the bin floor to receive grain directly from the sweep auger for discharge exteriorly of the bin.
---
paper_title: Algorithms in Real Algebraic Geometry

paper_content:

Algebraically Closed Fields.- Real Closed Fields.- Semi-Algebraic Sets.- Algebra.- Decomposition of Semi-Algebraic Sets.- Elements of Topology.- Quantitative Semi-algebraic Geometry.- Complexity of Basic Algorithms.- Cauchy Index and Applications.- Real Roots.- Cylindrical Decomposition Algorithm.- Polynomial System Solving.- Existential Theory of the Reals.- Quantifier Elimination.- Computing Roadmaps and Connected Components of Algebraic Sets.- Computing Roadmaps and Connected Components of Semi-algebraic Sets.
---
paper_title: On sign conditions over real multivariate polynomials

paper_content:

We present a new probabilistic algorithm to find a finite set of points intersecting the closure of each connected component of the realization of every sign condition over a family of real polynomials defining regular hypersurfaces that intersect transversally. This enables us to show a probabilistic procedure to list all feasible sign conditions over the polynomials. In addition, we extend these results to the case of closed sign conditions over an arbitrary family of real multivariate polynomials. The complexity bounds for these procedures improve the known ones.
---
paper_title: Polar varieties and computation of one point in each connected component of a smooth real algebraic set

paper_content:

Let f 1 , ldots, f s be polynomials in Q[X 1 , ..., X n ] that generate a radical ideal and let V be their complex zero-set. Suppose that V is smooth and equidimensional; then we show that computing suitable sections of the polar varieties associated to generic projections of V gives at least one point in each connected component of V ∩ Rn. We deduce an algorithm that extends that of Bank, Giusti, Heintz and Mbakop to non-compact situations. Its arithmetic complexity is polynomial in the complexity of evaluation of the input system, an intrinsic algebraic quantity and a combinatorial quantity.
---
paper_title: Properness defects of projections and computation of at least one point in each connected component of a real algebraic set

paper_content:

Computing at least one point in each connected component of a real algebraic set is a basic subroutine to decide emptiness of semi-algebraic sets, which is a fundamental algorithmic problem in effective real algebraic geometry. In this article we propose a new algorithm for the former task, which avoids a hypothesis of properness required in many of the previous methods. We show how studying the set of non-properness of a linear projection ź enables us to detect the connected components of a real algebraic set without critical points for ź. Our algorithm is based on this observation and its practical counterpoint, using the triangular representation of algebraic varieties. Our experiments show its efficiency on a family of examples.
---
paper_title: Polar varieties and efficient real elimination

paper_content:

Let \(S_0\) be a smooth and compact real variety given by a reduced regular sequence of polynomials \(f_1, \ldots, f_p\). This paper is devoted to the algorithmic problem of finding efficiently a representative point for each connected component of \(S_0\) . For this purpose we exhibit explicit polynomial equations that describe the generic polar varieties of \(S_0\). This leads to a procedure which solves our algorithmic problem in time that is polynomial in the (extrinsic) description length of the input equations \(f_1,\ldots, f_p\) and in a suitably introduced, intrinsic geometric parameter, called the degree of the real interpretation of the given equation system \(f_1,\ldots,f_p\).
---
paper_title: Polar varieties, real equation solving, and data structures: the hypersurface case

paper_content:

In this paper we apply for the first time a new method for multivariate equation solving which was developed in \cite{gh1}, \cite{gh2}, \cite{gh3} for complex root determination to the {\em real} case. Our main result concerns the problem of finding at least one representative point for each connected component of a real compact and smooth hypersurface. The basic algorithm of \cite{gh1}, \cite{gh2}, \cite{gh3} yields a new method for symbolically solving zero-dimensional polynomial equation systems over the complex numbers. One feature of central importance of this algorithm is the use of a problem--adapted data type represented by the data structures arithmetic network and straight-line program (arithmetic circuit). The algorithm finds the complex solutions of any affine zero-dimensional equation system in non-uniform sequential time that is {\em polynomial} in the length of the input (given in straight--line program representation) and an adequately defined {\em geometric degree of the equation system}. Replacing the notion of geometric degree of the given polynomial equation system by a suitably defined {\em real (or complex) degree} of certain polar varieties associated to the input equation of the real hypersurface under consideration, we are able to find for each connected component of the hypersurface a representative point (this point will be given in a suitable encoding). The input equation is supposed to be given by a straight-line program and the (sequential time) complexity of the algorithm is polynomial in the input length and the degree of the polar varieties mentioned above.
---
paper_title: On the Betti numbers of real varieties

paper_content:

PROOF. Approximate fi, * *, fm by real polynomials F1, * , Fm of the same degrees whose coefficients are algebraically independent. Now consider the variety Vc in the complex Cartesian space C'defined by the equations F1 =0, * * *, Fm =0. It follows from van der Waerden [9, ?41 ] that the number of points in Vc is equal to (deg fi) (deg f2) . . (deg fm). Since each point of V0 lies close to some real point of Vc; this proves Lemma 1.
---
paper_title: Counting connected components of a semialgebraic set in subexponential time

paper_content:

Let a semialgebraic set be defined by a quantifier-free formula with atomic subformulas of the form fi>0, 0,1 ≦ i ≦ where the polynomials fieℤ[X1,..., Xn] of degree deg (fi)<d have absolute value of the coefficients at most 2M. An algorithm is constructed which finds the connected components of the semialgebraic set (i.e., giving formulas for them) in a time that is polynomial inM (kd)ro(1). Collins' previously known method has a bound which is polynomial inM (kd)ro(1).
---
paper_title: Algorithms in Real Algebraic Geometry

paper_content:

Algebraically Closed Fields.- Real Closed Fields.- Semi-Algebraic Sets.- Algebra.- Decomposition of Semi-Algebraic Sets.- Elements of Topology.- Quantitative Semi-algebraic Geometry.- Complexity of Basic Algorithms.- Cauchy Index and Applications.- Real Roots.- Cylindrical Decomposition Algorithm.- Polynomial System Solving.- Existential Theory of the Reals.- Quantifier Elimination.- Computing Roadmaps and Connected Components of Algebraic Sets.- Computing Roadmaps and Connected Components of Semi-algebraic Sets.
---
paper_title: On Bounding the Betti Numbers and Computing the Euler Characteristic of Semi-algebraic Sets

paper_content:

Abstract. In this paper we prove new bounds on the sum of the Betti numbers of closed semi-algebraic sets and also give the first single exponential time algorithm for computing the Euler characteristic of arbitrary closed semi-algebraic sets. Given a closed semi-algebraic set S ::: $\subset$ Rk defined as the intersection of a real variety, Q=0, deg(Q)≤d, whose real dimension is k', with a set defined by a quantifier-free Boolean formula with no negations with atoms of the form Pi=0, Pi≥ 0, Pi≤ 0, deg(Pi) ≤ d, 1≤ i≤ s, we prove that the sum of the Betti numbers of S is bounded by sk'(O(d))k . This result generalizes the Oleinik—Petrovsky—Thom—Milnor bound in two directions. Firstly, our bound applies to arbitrary unions of basic closed semi-algebraic sets, not just for basic semi-algebraic sets. Secondly, the combinatorial part (the part depending on s ) in our bound, depends on the dimension of the variety rather than that of the ambient space. It also generalizes the result in [4] where a similar bound is proven for the number of connected components. We also prove that the sum of the Betti numbers of S is bounded by sk' 2O(k2 m4) in case the total number of monomials occurring in the polynomials in ::: $ {\cal P} \cup \{Q\}$ is m. Using the tools developed for the above results, as well as some additional techniques, we give the first single exponential time algorithm for computing the Euler characteristic of arbitrary closed semi-algebraic sets.
---
paper_title: Approximation of definable sets by compact families, and upper bounds on homotopy and homology

paper_content:

We prove new upper bounds on homotopy and homology groups of o-minimal sets in terms of ::: their approximations by compact o-minimal sets. In particular, we improve the known upper ::: bounds on Betti numbers of semialgebraic sets defined by quantifier-free formulae and obtain, ::: for the first time, a singly exponential bound on Betti numbers of sub-Pfaffian sets.
---
paper_title: Betti numbers of semi-algebraic sets defined by quantifier-free formulae

paper_content:

Let X be a semialgebraic set in Rn defined by a Boolean combination of atomic formulae of the kind h * 0 where * \in { >, \ge, = }, deg(h) < d, and the number of distinct polynomials h is k. We prove that the sum of Betti numbers of X is less than O(k2d)n.
---
paper_title: Computing the First Betti Number of a Semi-Algebraic Set

paper_content:

In this paper we describe a singly exponential algorithm for computing the first Betti number of a given semi-algebraic set. Singly exponential algorithms for computing the zeroth Betti number, and the Euler–Poincare characteristic, were known before. No singly exponential algorithm was known for computing any of the individual Betti numbers other than the zeroth one. As a consequence we also obtain algorithms for computing semi-algebraic descriptions of the semi-algebraically connected components of any given real algebraic or semi-algebraic set in singly exponential time, which improves on the complexity of the previously published algorithms for this problem.
---
paper_title: Computing the First Betti Number of a Semi-Algebraic Set

paper_content:

In this paper we describe a singly exponential algorithm for computing the first Betti number of a given semi-algebraic set. Singly exponential algorithms for computing the zeroth Betti number, and the Euler–Poincare characteristic, were known before. No singly exponential algorithm was known for computing any of the individual Betti numbers other than the zeroth one. As a consequence we also obtain algorithms for computing semi-algebraic descriptions of the semi-algebraically connected components of any given real algebraic or semi-algebraic set in singly exponential time, which improves on the complexity of the previously published algorithms for this problem.
---
paper_title: Computing the First Betti Number of a Semi-Algebraic Set

paper_content:

In this paper we describe a singly exponential algorithm for computing the first Betti number of a given semi-algebraic set. Singly exponential algorithms for computing the zeroth Betti number, and the Euler–Poincare characteristic, were known before. No singly exponential algorithm was known for computing any of the individual Betti numbers other than the zeroth one. As a consequence we also obtain algorithms for computing semi-algebraic descriptions of the semi-algebraically connected components of any given real algebraic or semi-algebraic set in singly exponential time, which improves on the complexity of the previously published algorithms for this problem.
---
paper_title: An Introduction to Algebraic Topology

paper_content:

A clear exposition, with exercises, of the basic ideas of algebraic topology. Suitable for a two-semester course at the beginning graduate level, it assumes a knowledge of point set topology and basic algebra. Although categories and functors are introduced early in the text, excessive generality is avoided, and the author explains the geometric or analytic origins of abstract concepts as they are introduced.
---
paper_title: Betti numbers of semi-algebraic sets defined by quantifier-free formulae

paper_content:

Let X be a semialgebraic set in Rn defined by a Boolean combination of atomic formulae of the kind h * 0 where * \in { >, \ge, = }, deg(h) < d, and the number of distinct polynomials h is k. We prove that the sum of Betti numbers of X is less than O(k2d)n.
---
paper_title: Computing the euler–poincaré characteristics of sign conditions

paper_content:

Computing various topological invariants of semi-algebraic sets in single exponential time is an active area of research. Several algorithms are known for deciding emptiness, computing the number of connected components of semi-algebraic sets in single exponential time etc. However, an algorithm for computing all the Betti numbers of a given semi-algebraic set in single exponential time is still lacking. In this paper we describe a new, improved algorithm for computing the Euler--Poincare characteristic (which is the alternating sum of the Betti numbers) of the realization of each realizable sign condition of a family of polynomials restricted to a real variety. The complexity of the algorithm is $$s^{k'+1}O(d)^{k} + s^{k'}((k' log_{2}(s) + k log_{2}(d))d)^{O(k)},$$ where s is the number of polynomials, k the number of variables, d a bound on the degrees, and k0 the real dimension of the variety. A consequence of our result is that the Euler--Poincare characteristic of any locally closed semi-algebraic set can be computed with the same complexity. The best previously known single exponential time algorithm for computing the Euler--Poincare characteristic of semi-algebraic sets worked only for a more restricted class of closed semi-algebraic sets and had a complexity of (ksd)O(k).
---
paper_title: On Bounding the Betti Numbers and Computing the Euler Characteristic of Semi-algebraic Sets

paper_content:

Abstract. In this paper we prove new bounds on the sum of the Betti numbers of closed semi-algebraic sets and also give the first single exponential time algorithm for computing the Euler characteristic of arbitrary closed semi-algebraic sets. Given a closed semi-algebraic set S ::: $\subset$ Rk defined as the intersection of a real variety, Q=0, deg(Q)≤d, whose real dimension is k', with a set defined by a quantifier-free Boolean formula with no negations with atoms of the form Pi=0, Pi≥ 0, Pi≤ 0, deg(Pi) ≤ d, 1≤ i≤ s, we prove that the sum of the Betti numbers of S is bounded by sk'(O(d))k . This result generalizes the Oleinik—Petrovsky—Thom—Milnor bound in two directions. Firstly, our bound applies to arbitrary unions of basic closed semi-algebraic sets, not just for basic semi-algebraic sets. Secondly, the combinatorial part (the part depending on s ) in our bound, depends on the dimension of the variety rather than that of the ambient space. It also generalizes the result in [4] where a similar bound is proven for the number of connected components. We also prove that the sum of the Betti numbers of S is bounded by sk' 2O(k2 m4) in case the total number of monomials occurring in the polynomials in ::: $ {\cal P} \cup \{Q\}$ is m. Using the tools developed for the above results, as well as some additional techniques, we give the first single exponential time algorithm for computing the Euler characteristic of arbitrary closed semi-algebraic sets.
---
paper_title: The complexity of elementary algebra and geometry

paper_content:

A tamper-evident top closure lid construction for a container. The lid is integrally formed from a plastic cover member, the member carrying a main and a secondary paperboard insert on its upper surface, the member and insert being bonded together. The plastic cover member has an integral tongue to define, upon tongue pivoting, an opening in the member. The main paperboard insert is hinged about a contiguous pivot axis. The secondary insert carries a pull tab. If formed from a brittle plastics material, pulling the pull tab breaks the plastics member at its tongue hinge. The pull tab is so formed as to indicate tampering to a prospective purchaser of the container provided with the top closure lid construction of this invention. The lid may also be provided with an upstanding rim to facilitate stacking.
---
paper_title: Complexity and Real Computation

paper_content:

1 Introduction.- 2 Definitions and First Properties of Computation.- 3 Computation over a Ring.- 4 Decision Problems and Complexity over a Ring.- 5 The Class NP and NP-Complete Problems.- 6 Integer Machines.- 7 Algebraic Settings for the Problem "P ? NP?".- 8 Newton's Method.- 9 Fundamental Theorem of Algebra: Complexity Aspects.- 10 Bezout's Theorem.- 11 Condition Numbers and the Loss of Precision of Linear Equations.- 12 The Condition Number for Nonlinear Problems.- 13 The Condition Number in ?(H(d).- 14 Complexity and the Condition Number.- 15 Linear Programming.- 16 Deterministic Lower Bounds.- 17 Probabilistic Machines.- 18 Parallel Computations.- 19 Some Separations of Complexity Classes.- 20 Weak Machines.- 21 Additive Machines.- 22 Nonuniform Complexity Classes.- 23 Descriptive Complexity.- References.
---
paper_title: Different bounds on the different Betti numbers of semi-algebraic sets

paper_content:

A classic result in real algebraic geometry due to Oleinik-Petrovsky, Thom and Milnor, bounds the {\em topological complexity} (the sum of the Betti numbers) of basic semi-algebraic sets. This bound is tight as one can construct examples having that many connected components. However, till now no significantly better bounds were known on the individual higher Betti numbers. In this paper we prove separate bounds on the different Betti numbers of basic semi-algebraic sets, as well as arrangements of algebraic hypersurfaces. These are the first results in this direction.
---
paper_title: Feasibility testing for systems of real quadratic equations

paper_content:

We consider the problem of deciding whether a given system of quadratic homogeneous equations over the reals has non-trivial solution. We design an approximative algorithm whose complexity is polynomial in the number of variables and exponential in the number of equations. Some applications to general systems of polynomial equations and inequalities over the reals are discussed.
---
paper_title: Polynomial Hierarchy, Betti Numbers and a Real Analogue of Toda's Theorem

paper_content:

Toda proved in 1989 that the (discrete) polynomial time hierarchy, $\mathbf{PH}$, is contained in the class $\mathbf{P}^{#\mathbf{P}}$, namely the class of languages that can be decided by a Turing machine in polynomial time given access to an oracle with the power to compute a function in the counting complexity class $#\mathbf{P}$. This result which illustrates the power of counting is considered to be a seminal result in computational complexity theory. An analogous result in the complexity theory over the reals (in the sense of Blum-Shub-Smale real machines) has been missing so far. In this paper we formulate and prove a real analogue of Toda's theorem. Unlike Toda's proof in the discrete case, which relied on sophisticated combinatorial arguments, our proof is topological in nature. As a consequence of our techniques we are also able to relate the computational hardness of two extremely well-studied problems in algorithmic semi-algebraic geometry -- namely the problem of deciding sentences in the first order theory of the reals with a constant number of quantifier alternations, and that of computing Betti numbers of semi-algebraic sets. We obtain a polynomial time reduction of the compact version of the first problem to the second. This latter result might be of independent interest to researchers in algorithmic semi-algebraic geometry.
---
paper_title: PP IS AS HARD AS THE POLYNOMIAL-TIME HIERARCHY*

paper_content:

In this paper, two interesting complexity classes, PP and $ \oplus {\text{P}}$, are compared with PH, the polynomial-time hierarchy. It is shown that every set in PH is polynomial-time Turing reducible to a set in PP, and PH is included in ${\text{BP}} \cdot \oplus {\text{P}}$. As a consequence of the results, it follows that ${\text{PP}} \subseteq {\text{PH}}$ (or $\oplus {\text{P}} \subseteq {\text{PH}}$) implies a collapse of PH. A stronger result is also shown: every set in PP(PH) is polynomial-time Turing reducible to a set in PP.
---
paper_title: Polynomial-time computing over quadratic maps I: sampling in real algebraic sets

paper_content:

Given a quadratic map $$Q:\mathbb{K}^n \to \mathbb{K}^k $$ defined over a computable subring D of a real closed field $$\mathbb{K},$$ and p ?D[Y1,...,Yk] of degree d, we consider the zero set $$Z = Z(p(Q(X)), \mathbb{K}^n) \subseteq \mathbb{K}^n$$ of p(Q(X1,...,Xn)) ?D[X1,...,Xn]. We present a procedure that computes, in (dn)O(k) arithmetic operations in D, a set $$\mathcal{S}$$ of (real univariate representations of) sampling points in $$\mathbb{K}^n$$ that intersects nontrivially each connected component of Z. As soon as k=o(n), this is faster than the known methods that all have exponential dependence on n in the complexity. In particular, our procedure is polynomial-time for constant k. In contrast, the best previously known procedure is only capable of deciding in $$n^{O(k^2 )} $$ operations the nonemptiness (rather than constructing sampling points) of the set Z in the case of p(Y)=?iYi2 and homogeneous Q. ::: ::: A by-product of our procedure is a bound (dn)O(k) on the number of connected components of Z. ::: ::: The procedure consists of exact symbolic computations in D and outputs vectors of algebraic numbers. It involves extending $$\mathbb{K}$$ by infinitesimals and subsequent limit computation by a novel procedure that utilizes knowledge of an explicit isomorphism between real algebraic sets.
---
paper_title: The Complexity of Stratification Computation

paper_content:

This paper investigates the complexity of stratification computation for semialgebraic sets. An upper bound for the computation of canonical stratifications is given for a wide class of stratifying conditions called here admissible. For such conditions, the stratifying process is at most doubly exponential in the depth of the stratification. Usual conditions of regularity like Whitney conditions (a) and (b) or Bekka condition (C) are admissible. A useful criterion and tools are given in order to prove easily other admissibilities.
---
paper_title: Complexity and Real Computation

paper_content:

1 Introduction.- 2 Definitions and First Properties of Computation.- 3 Computation over a Ring.- 4 Decision Problems and Complexity over a Ring.- 5 The Class NP and NP-Complete Problems.- 6 Integer Machines.- 7 Algebraic Settings for the Problem "P ? NP?".- 8 Newton's Method.- 9 Fundamental Theorem of Algebra: Complexity Aspects.- 10 Bezout's Theorem.- 11 Condition Numbers and the Loss of Precision of Linear Equations.- 12 The Condition Number for Nonlinear Problems.- 13 The Condition Number in ?(H(d).- 14 Complexity and the Condition Number.- 15 Linear Programming.- 16 Deterministic Lower Bounds.- 17 Probabilistic Machines.- 18 Parallel Computations.- 19 Some Separations of Complexity Classes.- 20 Weak Machines.- 21 Additive Machines.- 22 Nonuniform Complexity Classes.- 23 Descriptive Complexity.- References.
---
paper_title: Computational Complexity

paper_content:

Once we have developed an algorithm (q.v.) for solving a computational problem and analyzed its worst-case time requirements as a function of the size of its input (most usefully, in terms of the O-notation; see ALGORITHMS, ANALYSIS OF), it is inevitable to ask the question: "Can we do better?" In a typical problem, we may be able to devise new algorithms for the problem that are more and more efficient. But eventually, this line of research often seems to hit an invisible barrier, a level beyond whch improvements are very difficult, seemingly impossible, to come by. After many unsuccessful attempts, algorithm designers inevitably start to wonder if there is something inherent in the problem that makes it impossible to devise algorithms that are faster than the current one. They may try to develop mathematical techniques for proving formally that there can be no algorithm for the given problem which runs faster than the current one. Such a proof would be valuable, as it would suggest that it is futile to keep working on improved algorithms for this problem, that further improvements are certainly impossible. The realm of mathematical models and techniques for establishing such impossibility proofs is called computational complexity.
---
paper_title: Polynomial-time computing over quadratic maps I: sampling in real algebraic sets

paper_content:

Given a quadratic map $$Q:\mathbb{K}^n \to \mathbb{K}^k $$ defined over a computable subring D of a real closed field $$\mathbb{K},$$ and p ?D[Y1,...,Yk] of degree d, we consider the zero set $$Z = Z(p(Q(X)), \mathbb{K}^n) \subseteq \mathbb{K}^n$$ of p(Q(X1,...,Xn)) ?D[X1,...,Xn]. We present a procedure that computes, in (dn)O(k) arithmetic operations in D, a set $$\mathcal{S}$$ of (real univariate representations of) sampling points in $$\mathbb{K}^n$$ that intersects nontrivially each connected component of Z. As soon as k=o(n), this is faster than the known methods that all have exponential dependence on n in the complexity. In particular, our procedure is polynomial-time for constant k. In contrast, the best previously known procedure is only capable of deciding in $$n^{O(k^2 )} $$ operations the nonemptiness (rather than constructing sampling points) of the set Z in the case of p(Y)=?iYi2 and homogeneous Q. ::: ::: A by-product of our procedure is a bound (dn)O(k) on the number of connected components of Z. ::: ::: The procedure consists of exact symbolic computations in D and outputs vectors of algebraic numbers. It involves extending $$\mathbb{K}$$ by infinitesimals and subsequent limit computation by a novel procedure that utilizes knowledge of an explicit isomorphism between real algebraic sets.
---
paper_title: Computing the Top Betti Numbers of Semi-algebraic Sets Defined by Quadratic Inequalities in Polynomial Time

paper_content:

For any $\ell>0$, we present an algorithm which takes as input a semi-algebraic set, $S$, defined by $P_1 \leq 0,...,P_s \leq 0$, where each $P_i \in \R[X_1,...,X_k]$ has degree $\leq 2,$ and computes the top $\ell$ Betti numbers of $S$, $b_{k-1}(S), ..., b_{k-\ell}(S),$ in polynomial time. The complexity of the algorithm, stated more precisely, is $ \sum_{i=0}^{\ell+2} {s \choose i} k^{2^{O(\min(\ell,s))}}. $ For fixed $\ell$, the complexity of the algorithm can be expressed as $s^{\ell+2} k^{2^{O(\ell)}},$ which is polynomial in the input parameters $s$ and $k$. To our knowledge this is the first polynomial time algorithm for computing non-trivial topological invariants of semi-algebraic sets in $\R^k$ defined by polynomial inequalities, where the number of inequalities is not fixed and the polynomials are allowed to have degree greater than one. For fixed $s$, we obtain by letting $\ell = k$, an algorithm for computing all the Betti numbers of $S$ whose complexity is $k^{2^{O(s)}}$.
---
paper_title: Computing the Top Betti Numbers of Semi-algebraic Sets Defined by Quadratic Inequalities in Polynomial Time

paper_content:

For any $\ell>0$, we present an algorithm which takes as input a semi-algebraic set, $S$, defined by $P_1 \leq 0,...,P_s \leq 0$, where each $P_i \in \R[X_1,...,X_k]$ has degree $\leq 2,$ and computes the top $\ell$ Betti numbers of $S$, $b_{k-1}(S), ..., b_{k-\ell}(S),$ in polynomial time. The complexity of the algorithm, stated more precisely, is $ \sum_{i=0}^{\ell+2} {s \choose i} k^{2^{O(\min(\ell,s))}}. $ For fixed $\ell$, the complexity of the algorithm can be expressed as $s^{\ell+2} k^{2^{O(\ell)}},$ which is polynomial in the input parameters $s$ and $k$. To our knowledge this is the first polynomial time algorithm for computing non-trivial topological invariants of semi-algebraic sets in $\R^k$ defined by polynomial inequalities, where the number of inequalities is not fixed and the polynomials are allowed to have degree greater than one. For fixed $s$, we obtain by letting $\ell = k$, an algorithm for computing all the Betti numbers of $S$ whose complexity is $k^{2^{O(s)}}$.
---
paper_title: Complexity and Real Computation

paper_content:

1 Introduction.- 2 Definitions and First Properties of Computation.- 3 Computation over a Ring.- 4 Decision Problems and Complexity over a Ring.- 5 The Class NP and NP-Complete Problems.- 6 Integer Machines.- 7 Algebraic Settings for the Problem "P ? NP?".- 8 Newton's Method.- 9 Fundamental Theorem of Algebra: Complexity Aspects.- 10 Bezout's Theorem.- 11 Condition Numbers and the Loss of Precision of Linear Equations.- 12 The Condition Number for Nonlinear Problems.- 13 The Condition Number in ?(H(d).- 14 Complexity and the Condition Number.- 15 Linear Programming.- 16 Deterministic Lower Bounds.- 17 Probabilistic Machines.- 18 Parallel Computations.- 19 Some Separations of Complexity Classes.- 20 Weak Machines.- 21 Additive Machines.- 22 Nonuniform Complexity Classes.- 23 Descriptive Complexity.- References.
---
paper_title: Bounding the Betti numbers and computing the Euler-Poincar\'e characteristic of semi-algebraic sets defined by partly quadratic systems of polynomials

paper_content:

Let $\R$ be a real closed field, $ {\mathcal Q} \subset \R[Y_1,...,Y_\ell,X_1,...,X_k], $ with $ \deg_{Y}(Q) \leq 2, \deg_{X}(Q) \leq d, Q \in {\mathcal Q}, #({\mathcal Q})=m,$ and $ {\mathcal P} \subset \R[X_1,...,X_k] $ with $\deg_{X}(P) \leq d, P \in {\mathcal P}, #({\mathcal P})=s$, and $S \subset \R^{\ell+k}$ a semi-algebraic set defined by a Boolean formula without negations, with atoms $P=0, P \geq 0, P \leq 0, P \in {\mathcal P} \cup {\mathcal Q}$. We prove that the sum of the Betti numbers of $S$ is bounded by \[ \ell^2 (O(s+\ell+m)\ell d)^{k+2m}. \] This is a common generalization of previous results on bounding the Betti numbers of closed semi-algebraic sets defined by polynomials of degree $d$ and 2, respectively. ::: We also describe an algorithm for computing the Euler-Poincar\'e characteristic of such sets, generalizing similar algorithms known before. The complexity of the algorithm is bounded by $(\ell s m d)^{O(m(m+k))}$.
---
paper_title: Complexity of the mover's problem and generalizations

paper_content:

This paper concerns the problem of moving a polyhedron through Euclidean space while avoiding polyhedral obstacles.
---
paper_title: Polynomial-time computing over quadratic maps I: sampling in real algebraic sets

paper_content:

Given a quadratic map $$Q:\mathbb{K}^n \to \mathbb{K}^k $$ defined over a computable subring D of a real closed field $$\mathbb{K},$$ and p ?D[Y1,...,Yk] of degree d, we consider the zero set $$Z = Z(p(Q(X)), \mathbb{K}^n) \subseteq \mathbb{K}^n$$ of p(Q(X1,...,Xn)) ?D[X1,...,Xn]. We present a procedure that computes, in (dn)O(k) arithmetic operations in D, a set $$\mathcal{S}$$ of (real univariate representations of) sampling points in $$\mathbb{K}^n$$ that intersects nontrivially each connected component of Z. As soon as k=o(n), this is faster than the known methods that all have exponential dependence on n in the complexity. In particular, our procedure is polynomial-time for constant k. In contrast, the best previously known procedure is only capable of deciding in $$n^{O(k^2 )} $$ operations the nonemptiness (rather than constructing sampling points) of the set Z in the case of p(Y)=?iYi2 and homogeneous Q. ::: ::: A by-product of our procedure is a bound (dn)O(k) on the number of connected components of Z. ::: ::: The procedure consists of exact symbolic computations in D and outputs vectors of algebraic numbers. It involves extending $$\mathbb{K}$$ by infinitesimals and subsequent limit computation by a novel procedure that utilizes knowledge of an explicit isomorphism between real algebraic sets.
---
paper_title: Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials

paper_content:

Let $\R$ be a real closed field, $ {\mathcal Q} \subset \R[Y_1,...,Y_\ell,X_1,...,X_k], $ with $ °_{Y}(Q) \leq 2, °_{X}(Q) \leq d, Q \in {\mathcal Q}, #({\mathcal Q})=m,$ and $ {\mathcal P} \subset \R[X_1,...,X_k] $ with $°_{X}(P) \leq d, P \in {\mathcal P}, #({\mathcal P})=s$, and $S \subset \R^{\ell+k}$ a semi-algebraic set defined by a Boolean formula without negations, with atoms $P=0, P \geq 0, P \leq 0, P \in {\mathcal P} \cup {\mathcal Q}$. We prove that the sum of the Betti numbers of $S$ is bounded by $(\ell s m d)^{O(m+k)}$. This is a common generalization of previous results known before on bounding the Betti numbers of closed semi-algebraic sets defined by polynomials of degree $d$ and 2, respectively. ::: We also describe algorithms for computing the Euler-Poincare characteristic, as well as all the Betti numbers of such sets. The complexity of the first algorithm is bounded by $(\ell s m d)^{O(m(m+k))}$, while that of the second is bounded by $(\ell s m d)^{2^{O(m+k)}}$.
---
paper_title: A sum of squares approximation of nonnegative polynomials

paper_content:

We show that every real nonnegative polynomial $f$ can be approximated as closely as desired by a sequence of polynomials $\{f_\epsilon\}$ that are sums of squares. Each $f_\epsilon$ has a simple et explicit form in terms of $f$ and $\epsilon$. A special representation is also obtained for convex polynomials, nonnegative on a convex semi-algebraic set.
---
paper_title: Global Optimization with Polynomials and the Problem of Moments

paper_content:

We consider the problem of finding the unconstrained global minimum of a real-valued polynomial p(x): {\mathbb{R}}^n\to {\mathbb{R}}$, as well as the global minimum of p(x), in a compact set K defined by polynomial inequalities. It is shown that this problem reduces to solving an (often finite) sequence of convex linear matrix inequality (LMI) problems. A notion of Karush--Kuhn--Tucker polynomials is introduced in a global optimality condition. Some illustrative examples are provided.
---
paper_title: Sums of squares, moment matrices and optimization over polynomials

paper_content:

We consider the problem of minimizing a polynomial over a semialgebraic set defined by polynomial equations and inequalities, which is NP-hard in general. Hierarchies of semidefinite relaxations have been proposed in the literature, involving positive semidefinite moment matrices and the dual theory of sums of squares of polynomials. We present these hierarchies of approximations and their main properties: asymptotic/finite convergence, optimality certificate, and extraction of global optimum solutions. We review the mathematical tools underlying these properties, in particular, some sums of squares representation results for positive polynomials, some results about moment matrices (in particular, of Curto and Fialkow), and the algebraic eigenvalue method for solving zero-dimensional systems of polynomial equations. We try whenever possible to provide detailed proofs and background.
---
paper_title: Interior-Point Polynomial Algorithms in Convex Programming

paper_content:

Written for specialists working in optimization, mathematical programming, or control theory. The general theory of path-following and potential reduction interior point polynomial time methods, interior point methods, interior point methods for linear and quadratic programming, polynomial time methods for nonlinear convex programming, efficient computation methods for control problems and variational inequalities, and acceleration of path-following methods are covered. In this book, the authors describe the first unified theory of polynomial-time interior-point methods. Their approach provides a simple and elegant framework in which all known polynomial-time interior-point methods can be explained and analyzed; this approach yields polynomial-time interior-point methods for a wide variety of problems beyond the traditional linear and quadratic programs. The book contains new and important results in the general theory of convex programming, e.g., their "conic" problem formulation in which duality theory is completely symmetric. For each algorithm described, the authors carefully derive precise bounds on the computational effort required to solve a given family of problems to a given precision. In several cases they obtain better problem complexity estimates than were previously known. Several of the new algorithms described in this book, e.g., the projective method, have been implemented, tested on "real world" problems, and found to be extremely efficient in practice. Contents : Chapter 1: Self-Concordant Functions and Newton Method; Chapter 2: Path-Following Interior-Point Methods; Chapter 3: Potential Reduction Interior-Point Methods; Chapter 4: How to Construct Self- Concordant Barriers; Chapter 5: Applications in Convex Optimization; Chapter 6: Variational Inequalities with Monotone Operators; Chapter 7: Acceleration for Linear and Linearly Constrained Quadratic Problems
---
paper_title: Convergent SDP-Relaxations in Polynomial Optimization with Sparsity

paper_content:

We consider a polynomial programming problem P on a compact basic semi-algebraic set K⊂ℝn, described by m polynomial inequalities gj(X)≥0, and with criterion f∈ℝ[X]. We propose a hierarchy of semidefinite relaxations that take sparsity of the original data into account, in the spirit of those of Waki et al. [7]. The novelty with respect to [7] is that we prove convergence to the global optimum of P when the sparsity pattern satisfies a condition often encountered in large size problems of practical applications, and known as the running intersection property in graph theory.
---
paper_title: Semidefinite programming relaxations for semialgebraic problems

paper_content:

A hierarchy of convex relaxations for semialgebraic problems is introduced. For questions reducible to a finite number of polynomial equalities and inequalities, it is shown how to construct a complete family of polynomially sized semidefinite programming conditions that prove infeasibility. The main tools employed are a semidefinite programming formulation of the sum of squares decomposition for multivariate polynomials, and some results from real algebraic geometry. The techniques provide a constructive approach for finding bounded degree solutions to the Positivstellensatz, and are illustrated with examples from diverse application fields.
---
paper_title: Complexity and Real Computation

paper_content:

1 Introduction.- 2 Definitions and First Properties of Computation.- 3 Computation over a Ring.- 4 Decision Problems and Complexity over a Ring.- 5 The Class NP and NP-Complete Problems.- 6 Integer Machines.- 7 Algebraic Settings for the Problem "P ? NP?".- 8 Newton's Method.- 9 Fundamental Theorem of Algebra: Complexity Aspects.- 10 Bezout's Theorem.- 11 Condition Numbers and the Loss of Precision of Linear Equations.- 12 The Condition Number for Nonlinear Problems.- 13 The Condition Number in ?(H(d).- 14 Complexity and the Condition Number.- 15 Linear Programming.- 16 Deterministic Lower Bounds.- 17 Probabilistic Machines.- 18 Parallel Computations.- 19 Some Separations of Complexity Classes.- 20 Weak Machines.- 21 Additive Machines.- 22 Nonuniform Complexity Classes.- 23 Descriptive Complexity.- References.
---
paper_title: Semidefinite programming and arithmetic circuit evaluation

paper_content:

A rational number can be naturally presented by an arithmetic computation (AC): a sequence of elementary arithmetic operations starting from a fixed constant, say 1. The asymptotic complexity issues of such a representation are studied e.g. in the framework of the algebraic complexity theory over arbitrary field. Here we study a related problem of the complexity of performing arithmetic operations and computing elementary predicates, e.g. ``='' or ``>'', on rational numbers given by AC. In the first place, we prove that AC can be efficiently simulated by the exact semidefinite programming (SDP). Secondly, we give a BPP-algorithm for the equality predicate. Thirdly, we put ``>''-predicate into the complexity class PSPACE. We conjecture that ``>''-predicate is hard to compute. This conjecture, if true, would clarify the complexity status of the exact SDP - a well known open problem in the field of mathematical programming.
---
paper_title: On the Complexity of Semidefinite Programs

paper_content:

AbstractWe show that the feasibility of a system of m linear inequalities over the cone of symmetric positive semidefinite matrices of order n can be tested in mn ::: $$mn^{o(\min \{ m,n^2 \} )} $$ ::: arithmetic operations with ::: $$ln^{o(\min \{ m,n^2 \} )} $$ ::: -bit numbers, where l is the maximum binary size of the input coefficients. We also show that any feasible system of dimension (m,n) has a solution X such that log||X|| ≤ ::: $$ln^{o(\min \{ m,n^2 \} )} $$ ::: .
---
paper_title: An exact duality theory for semidefinite programming and its complexity implications

paper_content:

In this paper, we present a new and more complete duality for Semidefinite Programming (SDP), with the following features: \begin{itemize} \item This dual is an explicit semidefinite program, whose number of variables and the coefficient bitlengths are polynomial in those of the primal. \item If the Primal is feasible, then it is bounded if and only if the dual is feasible. \item The duality gap, \ie the difference between the primal and the dual objective function values, is zero whenever the primal is feasible and bounded. Also, in this case, the dual attains its optimum \item It yields a precise Farkas Lemma for semidefinite feasibility systems, \ie characterization of the {\it infeasibility} of a semidefinite inequality in terms of the {\it feasibility} of another polynomial size semidefinite inequality. \end{itemize} Note that the standard duality for Linear Programming satisfies all of the above features, but no such duality theory was previously known for SDP, without Slater-like conditions being assumed. Then we apply the dual to derive certain complexity results for Semidefinite Programming Problems. The decision problem of Semidefinite Feasibility (SDFP), \ie that of determining if a given semidefinite inequality system is feasible, is the central problem of interest. The complexity of SDFP is unknown, but we show the following: 1) In the Turing machine model, SDFP is not NP-Complete unless NP=Co-NP; 2) In the real number model of Blum, Shub and Smale\cite{bss}, SDFP is in NP$\cap$Co-NP. We then give polynomial reductions from the following problems to SDFP: 1) Checking whether an SDP is bounded; 2) Checking whether a feasible and bounded SDP attains the optimum; 3) Checking the optimality of a feasible solution.
---
paper_title: Geodesic diameter of sets defined by few quadratic equations and inequalities

paper_content:

We prove a bound for the geodesic diameter of a subset of the unit ball in \({\mathbb{R}^n}\) described by a fixed number of quadratic equations and inequalities, which is polynomial in n, whereas the known bound for general degree is exponential in n. Our proof uses methods borrowed from D’Acunto and Kurdyka (to deal with the geodesic diameter) and from Barvinok (to take advantage of the quadratic nature).
---
paper_title: Polynomial Hierarchy, Betti Numbers and a Real Analogue of Toda's Theorem

paper_content:

Toda proved in 1989 that the (discrete) polynomial time hierarchy, $\mathbf{PH}$, is contained in the class $\mathbf{P}^{#\mathbf{P}}$, namely the class of languages that can be decided by a Turing machine in polynomial time given access to an oracle with the power to compute a function in the counting complexity class $#\mathbf{P}$. This result which illustrates the power of counting is considered to be a seminal result in computational complexity theory. An analogous result in the complexity theory over the reals (in the sense of Blum-Shub-Smale real machines) has been missing so far. In this paper we formulate and prove a real analogue of Toda's theorem. Unlike Toda's proof in the discrete case, which relied on sophisticated combinatorial arguments, our proof is topological in nature. As a consequence of our techniques we are also able to relate the computational hardness of two extremely well-studied problems in algorithmic semi-algebraic geometry -- namely the problem of deciding sentences in the first order theory of the reals with a constant number of quantifier alternations, and that of computing Betti numbers of semi-algebraic sets. We obtain a polynomial time reduction of the compact version of the first problem to the second. This latter result might be of independent interest to researchers in algorithmic semi-algebraic geometry.
---
paper_title: Bounds For Gradient Trajectories and Geodesic Diameter of Real Algebraic Sets

paper_content:

Let $M\subset \mathbb{R}^n$ be a connected component of an algebraic set $\varphi^{-1}(0)$ , where $\varphi$ is a polynomial of degree $d$ . Assume that $M$ is contained in a ball of radius $r$ . We prove that the geodesic diameter of $M$ is bounded by $2r\nu(n)d(4d-5)^{n-2}$ , where $\nu(n)=2{\Gamma({1}/{2})\Gamma(({n+1})/{2})}{\Gamma({n}/{2})}^{-1}$ . This estimate is based on the bound $r\nu(n)d(4d-5)^{n-2}$ for the length of the gradient trajectories of a linear projection restricted to $M$ .
---

Title: ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY

Section 1: Introduction
Description 1: Discuss the survey's objectives, historical context, and notation used in the paper.

Section 2: Main Algorithmic Problems
Description 2: Outline the primary types of algorithmic problems in semi-algebraic geometry, splitting them into logical and geometric/topological categories.

Section 3: Quantifier Elimination and Related Problems
Description 3: Describe the historical development and methodologies for quantifier elimination, including Tarski's algorithm, Cylindrical Algebraic Decomposition, and critical points method.

Section 4: Computing Topological Invariants of Semi-Algebraic Sets
Description 4: Discuss algorithms for computing various topological invariants like connectivity, Euler-Poincaré characteristic, and Betti numbers, highlighting techniques like roadmaps and parametrized paths.

Section 5: Numerical Algorithms for Polynomial Optimization
Description 5: Detail numerical approaches for polynomial optimization using the "sums-of-squares" method and semi-definite programming techniques, along with their computational complexity.

Section 6: Open Problems
Description 6: List and describe significant open problems in the field, such as computing Betti numbers in singly exponential time and finding more efficient algorithms for connected components.

Section 7: Acknowledgment
Description 7: Mention the support received for the research, including any grants or institutional support.