Fetching the paper…
Reading the bibliography…
We survey both old and new developments in the theory of algorithms in real algebraic geometry -- starting from effective quantifier elimination in the first order theory of reals due to Tarski and Seidenberg, to more recent algorithms for computing topological invariants of semi-algebraic sets.
On the topology of real algebraic surfaces
I. G. Petrovskiĭ and O. A. Oleĭnik · 1949
Earlier work this paper cites.
A decision method for elementary algebra and geometry
A. Tarski · 1951
Earlier work this paper cites.
Triangulation of semi-analytic sets
S. Lojasiewicz · 1964
Earlier work this paper cites.
On the Betti numbers of real varieties
J. Milnor · 1964
Earlier work this paper cites.
Sur l’homologie des variétés algébriques réelles
R. Thom · 1965
Earlier work this paper cites.
Quantifier elimination for real closed fields by cylindrical algebraic decomposition
G. Collins · 1975
Earlier work this paper cites.
Quantifier elimination for real closed fields by cylindric algebraic decomposition
G. E. Collins · 1975
Earlier work this paper cites.
Elementary-recursive decision procedures
L. G. Monk · 1975
Earlier work this paper cites.
Ein Entschiedungsverfahren für die Theorie der reell-abgeschlossenen Körper
H. R. Wüthrich · 1976
Earlier work this paper cites.
Complexity of the mover’s problem and generalizations
J. Reif · 1979
Earlier work this paper cites.
Semi-algebraic local-triviality in semi-algebraic mappings
R. Hardt · 1980
Earlier work this paper cites.
On the piano movers’ problem ii. general techniques for computing topological properties of real algebraic manifolds
J. Schwartz and M. Sharir · 1983
Earlier work this paper cites.
The complexity of elementary algebra and geometry
M. Ben-Or, D. Kozen, and J. Reif · 1986
Earlier work this paper cites.
Thom’s lemma, the coding of real algebraic numbers and the topology of semi-algebraic sets
M. Coste and M.-F. Roy · 1988
Earlier work this paper cites.
Real quantifier elimination is doubly exponential
J. H. Davenport and J. Heintz · 1988
Earlier work this paper cites.
Solving systems of polynomial inequalities in subexponential time
D. Y. Grigoriev and N. N. Vorobjov, Jr · 1988
Earlier work this paper cites.
An Introduction to Algebraic Topology
J. J. Rotman · 1988
Earlier work this paper cites.
Complexity of the computations with real algebraic numbers
M.-F. Roy and A. Szpirglas · 1990
Earlier work this paper cites.
PP is as hard as the polynomial-time hierarchy
S. Toda · 1991
Earlier work this paper cites.
Counting connected components of a semi-algebraic set in subexponential time
D. Grigoriev and N. Vorobjov · 1992
Earlier work this paper cites.
On the computational complexity and geometry of the first-order theory of the reals. I-III
J. Renegar · 1992
Earlier work this paper cites.
Feasibility testing for systems of real quadratic equations
A. I. Barvinok · 1993
Earlier work this paper cites.
Computing road maps in general semi-algebraic sets
J. Canny · 1993
Earlier work this paper cites.
Construction of roadmaps of semi-algebraic sets
L. Gournay and J. J. Risler · 1993
Earlier work this paper cites.
Description of the connected components of a semialgebraic set in single exponential time
J. Heintz, M.-F. Roy, and P. Solernò · 1994
Earlier work this paper cites.
Interior-point polynomial algorithms in convex programming
Y. Nesterov and A. Nemirovskii · 1994
Earlier work this paper cites.
Computational Complexity
C. Papadimitriou · 1994
Earlier work this paper cites.
Topological methods
A. Björner · 1995
Earlier work this paper cites.
Sums of squares of real polynomials
M. D. Choi, T. Y. Lam, and B. Reznick · 1995
Earlier work this paper cites.
On the combinatorial and algebraic complexity of quantifier elimination
S. Basu, R. Pollack, and M.-F. Roy · 1996
Earlier work this paper cites.
Polar varieties, real equation solving, and data structures: the hypersurface case
B. Bank, M. Giusti, J. Heintz, and G. M. Mbakop · 1997
Cited alongside, same era.
On the Betti numbers of semialgebraic sets defined by few quadratic inequalities
A. I. Barvinok · 1997
Cited alongside, same era.
On computing a set of points meeting every cell defined by a family of polynomials on a variety
S. Basu, R. Pollack, and M.-F. Roy · 1997
Cited alongside, same era.
On the complexity of semidefinite programs
L. Porkolab and L. Khachiyan · 1997
Cited alongside, same era.
An exact duality theory for semidefinite programming and its complexity implications
M. V. Ramana · 1997
Cited alongside, same era.
Relational expressive power of constraint query languages
M. Benedikt, G. Dong, L. Libkin, and L. Wong · 1998
Convergent SDP-relaxations in polynomial optimization with sparsity
J. B. Lasserre · 2006
Later among the works it cites.
A sum of squares approximation of nonnegative polynomials
J. B. Lasserre · 2006
Later among the works it cites.
On the number of homotopy types of fibres of a definable map
S. Basu and N. Vorobjov · 2007
Later among the works it cites.
Computing the top few Betti numbers of semi-algebraic sets defined by quadratic inequalities in polynomial time
S. Basu · 2008
Later among the works it cites.
A sharper estimate on the Betti numbers of sets defined by quadratic inequalities
S. Basu and M. Kettner · 2008
Later among the works it cites.
Computing the first Betti number of a semi-algebraic set
S. Basu, R. Pollack, and M.-F. Roy · 2008
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Complexity and real computation
L. Blum, F. Cucker, M. Shub, and S. Smale · 1998
Cited alongside, same era.
Géométrie algébrique réelle (Second edition in english: Real Algebraic Geometry)
J. Bochnak, M. Coste, and M.-F. Roy · 1998
Cited alongside, same era.
An algorithm for sums of squares of real polynomials
V. Powers and T. Wörmann · 1998
Cited alongside, same era.
The complexity of stratification computation
E. Rannou · 1998
Cited alongside, same era.
New results on quantifier elimination over real closed fields and applications to constraint databases
S. Basu · 1999
Cited alongside, same era.
On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets
S. Basu · 1999
Cited alongside, same era.
Certificates of positivity in the Bernstein basis
F. Boudaoud, F. Caruso, and M.-F. Roy · 2008
Later among the works it cites.
Semidefinite programming and arithmetic circuit evaluation
S. P. Tarasov and M. N. Vyalyi · 2008
Later among the works it cites.
Computing the Betti numbers of semi-algebraic sets defined by partly quadratic sytems of polynomials
S. Basu, D. V. Pasechnik, and M.-F. Roy · 2009
Later among the works it cites.
Approximation of definable sets by compact families, and upper bounds on homotopy and homology
A. Gabrielov and N. Vorobjov · 2009
Later among the works it cites.
Sums of squares, moment matrices and optimization over polynomials
M. Laurent · 2009
Later among the works it cites.
On the geometry of polar varieties
B. Bank, M. Giusti, J. Heintz, M. Safey El Din, and É. Schost · 2010
Later among the works it cites.
Bounding the Betti numbers and computing the Euler-Poincaré characteristic of semi-algebraic sets defined by partly quadratic systems of polynomials
S. Basu, D. V. Pasechnik, and M.-F. Roy · 2010
Later among the works it cites.
Bounding the radii of balls meeting every connected component of semi-algebraic sets
S. Basu and M.-F. Roy · 2010
Later among the works it cites.
Polynomial hierarchy, Betti numbers, and a real analogue of Toda’s theorem
S. Basu and T. Zell · 2010
Later among the works it cites.
On the minimum of a positive polynomial over the standard simplex
G. Jeronimo and D. Perrucci · 2010
Later among the works it cites.
On sign conditions over real multivariate polynomials
G. Jeronimo, D. Perrucci, and J. Sabia · 2010
Later among the works it cites.
A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface
M. Safey El Din and É. Schost · 2010
Later among the works it cites.
Refined bounds on the number of connected components of sign conditions on a variety
S. Barone and S. Basu · 2011
Later among the works it cites.
Linear solving for sign determination
D. Perrucci · 2011
Later among the works it cites.
Systems of quadratic inequalities
A. Agrachev and A. Lerario · 2012
Later among the works it cites.
A baby step-giant step roadmap algorithm for general algebraic sets
S. Basu, M.-F. Roy, M. Safey El Din, and É. Schost · 2012
Later among the works it cites.
Unit distances in three dimensions
H. Kaplan, J. Matoušek, M. Sharir, and S. Safernová · 2012
Later among the works it cites.
A complexity theory of constructible functions and sheaves
S. Basu · 2013
Later among the works it cites.
Monotone functions and maps
S. Basu, A. Gabrielov, and N. Vorobjov · 2013
Later among the works it cites.
On the minimum of a polynomial function on a basic closed semialgebraic set and applications
G. Jeronimo, D. Perrucci, and E. Tsigaridas · 2013
Later among the works it cites.
M. Safey El Din and É. Schost · 2013
Later among the works it cites.
An improved bound on the number of point-surface incidences in three dimensions
J. Zahl · 2013
Later among the works it cites.
Divide and conquer roadmap for algebraic sets
S. Basu and M.-F. Roy · 2014
Closest in time.