The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.
Algorithms in Real Algebraic Geometry
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Existential Theory of the Reals
(2006) · Algorithms and computation in mathematics · doi:10.1007/3-540-33099-2_14 · Cited by 7
Computing Roadmaps and Connected Components of Semi-algebraic Sets
Basu, S., Pollack, R. M., & Roy, M.-F. (2003) · Algorithms and computation in mathematics · doi:10.1007/978-3-662-05355-3_17 · Cited by 1
Self-citationQuantitative Semi-algebraic Geometry
(2006) · Springer eBooks · doi:10.1007/3-540-33099-2_8 · Cited by 1
Cited by
Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods
Drusvyatskiy, D., & Lewis, A. S. (2018) · Mathematics of Operations Research · doi:10.1287/moor.2017.0889 · Cited by 267
Jovanović, D., & de Moura, L. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-31365-3_27 · Cited by 240
Controller Synthesis Free of Analytical Models: Three Term Controllers
Keel, L. H., & Bhattacharyya, S. P. (2008) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2008.925810 · Cited by 167
A combinatorial approach to planar non-colliding robot arm motion planning
Ileana Streinu, E. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892132 · Cited by 149
Likelihood ratio tests and singularities
Drton, M. (2009) · The Annals of Statistics · doi:10.1214/07-aos571 · Cited by 133
“In-depth treatments can be found in [2, 3, 5].”
Müller, S., Feliu, E., Regensburger, G., Conradi, C., Shiu, A., & Dickenstein, A. (2015) · Foundations of Computational Mathematics · doi:10.1007/s10208-014-9239-3 · Cited by 149
NP-hardness of deciding convexity of quartic polynomials and related problems
Ahmadi, A. A., Olshevsky, A., Parrilo, P. A., & Tsitsiklis, J. N. (2011) · Mathematical Programming · doi:10.1007/s10107-011-0499-2 · Cited by 126
“Unfortunately, algorithms based on quantifier elimination or similar decision algebra techniques have running times that are at least exponential in the number of variables [5], and in practice can only solve problems with very few parameters.”
BackgroundMethodInfluentialComputing cylindrical algebraic decomposition via triangular decomposition
Chen, C., Maza, M. M., Xia, B., et al. (2009) · International Symposium on Symbolic and Algebraic Computation · doi:10.1145/1576702.1576718 · Cited by 104
On the Quantum Chromatic Number of a Graph
Cameron, P. J., Montanaro, A., Newman, M., Simone Severini, B., & Winter, A. (2007) · The Electronic Journal of Combinatorics · doi:10.37236/999 · Cited by 119
“This has bearing on the decidability of the quantum chromatic number: the problem if χ (r) q (G) ≤ c is decidable because it boils down to solving the set of quadratic equations (1) over the reals in a space of dimension cr, for which there exist exact algorithms based on extensions of the Gröbner basis technique [2].”
MethodThe “Price of Anarchy” Under Nonlinear and Asymmetric Costs
Perakis, G. (2007) · Mathematics of Operations Research · doi:10.1287/moor.1070.0258 · Cited by 94
Fixed Points, Nash Equilibria, and the Existential Theory of the Reals
Schaefer, M., & Štefankovič, D. (2015) · Theory of Computing Systems · doi:10.1007/s00224-015-9662-0 · Cited by 92
Fast and exact geometric analysis of real algebraic plane curves
Eigenwillig, A., Kerber, M., & Wolpert, N. (2007) · International Symposium on Symbolic and Algebraic Computation · doi:10.1145/1277548.1277570 · Cited by 91
Location of the last stable orbit in Kerr spacetime
Stein, L. C., & Warburton, N. (2020) · Physical review. D/Physical review. D. · doi:10.1103/physrevd.101.064007 · Cited by 85
Numerical algebraic geometry and algebraic kinematics
Wampler, C. W., & Sommese, A. J. (2011) · Acta Numerica · doi:10.1017/s0962492911000067 · Cited by 83
The Number of Embeddings of Minimally Rigid Graphs
Borcea, C. S., & Streinu, I. (2004) · Discrete & Computational Geometry · doi:10.1007/s00454-003-2902-0 · Cited by 82
On the asymptotic and practical complexity of solving bivariate systems over the reals
Diochnos, D. I., Emiris, I. Z., & Tsigaridas, E. (2008) · Journal of Symbolic Computation · doi:10.1016/j.jsc.2008.04.009 · Cited by 79
Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Nonlinear Equations
Etessami, K., & Yannakakis, M. (2005) · Lecture notes in computer science · doi:10.1007/978-3-540-31856-9_28 · Cited by 78
Din, M. S. E., & Schost, É. (2017) · Journal of the ACM · doi:10.1145/2996450 · Cited by 77
“The initial motivation of Canny’s work was to motion planning, but computing roadmaps actually became the key to further algorithms in semi-algebraic geometry, such as computing a decomposition of a semialgebraic set into its semi-algebraically connected components [Basu et al. 2006].”
Learning control lyapunov functions from counterexamples and demonstrations
Ravanbakhsh, H., & Sankaranarayanan, S. (2018) · Autonomous Robots · doi:10.1007/s10514-018-9791-9 · Cited by 109
Computing 2-Hop Neighborhoods in Ad Hoc Wireless Networks
Cälinescu, G. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-39611-6_16 · Cited by 74
Sanyal, R., Sottile, F., & Sturmfels, B. (2011) · Mathematika · doi:10.1112/s002557931100132x · Cited by 73
Quantifier Elimination by Lazy Model Enumeration
Monniaux, D. P. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-14295-6_51 · Cited by 77
Essential Convexity and Complexity of Semi-Algebraic Constraints
Bodirsky, M., Jönsson, P., & von Oertzen, T. (2012) · Logical Methods in Computer Science · doi:10.2168/lmcs-8(4:5)2012 · Cited by 77
On the number of zeros of Abelian integrals
Binyamini, G., Novikov, D., & Yakovenko, S. Y. (2010) · Inventiones mathematicae · doi:10.1007/s00222-010-0244-0 · Cited by 72
“The latter condition is topological (selection of a connected component in a suitable configuration space), and it is known that all connected components of semialgebraic sets are themselves semialgebraic and effectively constructible [5].”
BackgroundNumerically Computing Real Points on Algebraic Sets
Hauenstein, J. D. (2012) · Acta Applicandae Mathematicae · doi:10.1007/s10440-012-9782-3 · Cited by 63
On the Complexity of Nonlinear Mixed-Integer Optimization
Köppe, M. (2011) · The IMA volumes in mathematics and its applications · doi:10.1007/978-1-4614-1927-3_19 · Cited by 65
Variant quantifier elimination
Hong, H., & Din, M. S. E. (2011) · Journal of Symbolic Computation · doi:10.1016/j.jsc.2011.05.014 · Cited by 67
Sphere and Dot Product Representations of Graphs
Kang, R. J., & Müller, T. (2012) · Discrete & Computational Geometry · doi:10.1007/s00454-012-9394-8 · Cited by 66
A Geometrical–Statistical Approach to Outlier Removal for TDOA Measurements
Compagnoni, M., Pini, A., Canclini, A., Bestagini, P., Antonacci, F., Tubaro, S., & Sarti, A. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2701311 · Cited by 70
The Inverse Moment Problem for Convex Polytopes
Gravin, N., Lasserre, J. B., Ṗasechnik, D. V., et al. (2012) · Discrete & Computational Geometry · doi:10.1007/s00454-012-9426-4 · Cited by 60
Computation in Real Closed Infinitesimal and Transcendental Extensions of the Rationals
de Moura, L., & Passmore, G. O. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38574-2_12 · Cited by 60
An algebraic approach to continuous collision detection for ellipsoids
Jia, X., Choi, Y., Mourrain, B., et al. (2011) · Computer Aided Geometric Design · doi:10.1016/j.cagd.2011.01.004 · Cited by 60
Jones, N. S., & Linden, N. (2005) · Physical Review A · doi:10.1103/physreva.71.012324 · Cited by 60
“ar X iv :q ua nt -p h/ 04 07 11 7v 1 1 5 Ju l 2 00”
Realizability of Graphs and Linkages
Schaefer, M. (2012) · Springer eBooks · doi:10.1007/978-1-4614-0110-0_24 · Cited by 60
Berthomieu, J., Eder, C., & Din, M. S. E. (2021) · International Symposium on Symbolic and Algebraic Computation · doi:10.1145/3452143.3465545 · Cited by 57
Bounded-Degree Graphs can have Arbitrarily Large Slope Numbers
Pach, J., & Pálvölgyi, D. (2006) · The Electronic Journal of Combinatorics · doi:10.37236/1139 · Cited by 57
Triangular decomposition of semi-algebraic systems
Chen, C., Davenport, J. H., May, J. P., et al. (2011) · Journal of Symbolic Computation · doi:10.1016/j.jsc.2011.12.014 · Cited by 57
Quantifier elimination by cylindrical algebraic decomposition based on regular chains
Chen, C., & Maza, M. M. (2015) · Journal of Symbolic Computation · doi:10.1016/j.jsc.2015.11.008 · Cited by 55
Tropicalizing the Simplex Algorithm
Allamigeon, X., Benchimol, P., Gaubert, S., et al. (2015) · SIAM Journal on Discrete Mathematics · doi:10.1137/130936464 · Cited by 56
On the Topology of Real Algebraic Plane Curves
Cheng, J.-S., Lazard, S., Peñaranda, L., et al. (2010) · Mathematics in Computer Science · doi:10.1007/s11786-010-0044-3 · Cited by 54
“To this end, most algorithms [1,3,8,18,26,30,32,33,41,46,48] rely heavily on computations with real algebraic numbers, Sturm sequences or sub-resultant sequences.”
BackgroundMethodA small frame and a certificate of its injectivity
Vinzant, C. (2015) · International Conference on Sampling Theory and Applications · doi:10.1109/sampta.2015.7148879 · Cited by 53
Weighted low rank approximations with provable guarantees
Razenshteyn, I., Song, Z., & Woodruff, D. P. (2016) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2897518.2897639 · Cited by 51
“However, when we try to solve for U in terms of V we face the same problem again: we can write U as E ·U ′, where U ′ only has polynomial entries, but since we do not assume a small number of distinct rows of W , it follows that E could have n distinct entries 1det(U>D Wi S>SD Wi U) for i = 1, . .…”
BackgroundMehlhorn, K., Sagraloff, M., & Wang, P. (2014) · Journal of Symbolic Computation · doi:10.1016/j.jsc.2014.02.001 · Cited by 52
“In this section, we show how to integrate our approach to isolate and approximate the roots of a univariate polynomial in an algorithm to compute a cylindrical algebraic decomposition [3,4,5,21,13,25,46,15,28,10].”
MethodExact algorithms for solving stochastic games
Hansen, K. A., Koucký, M., Lauritzen, N., et al. (2011) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1993636.1993665 · Cited by 50
“We use Theorem 14.16 (Quanti.er Elimination) of Basu, Pollack and Roy [2] on the formula of Theorem 15 to .nd a quanti.er free formula expressing that v is the value vector of the game.”
BackgroundMethodInfluentialUndecidability and hardness in mixed-integer nonlinear programming
Liberti, L. (2018) · RAIRO - Operations Research · doi:10.1051/ro/2018036 · Cited by 53
Complexity of real root isolation using continued fractions
Sharma, V. (2008) · Theoretical Computer Science · doi:10.1016/j.tcs.2008.09.017 · Cited by 49
Formal proofs in real algebraic geometry: from ordered fields to quantifier elimination
Mahboubi, A., & Cohen, C. (2012) · Logical Methods in Computer Science · doi:10.2168/lmcs-8(1:2)2012 · Cited by 50
Acute Triangulations of Polygons
Streinu, I. (2005) · Discrete & Computational Geometry · doi:10.1007/s00454-005-1184-0 · Cited by 46
Nash Equilibria via Polynomial Equations
Lipton, R. J., & Markakis, E. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24698-5_45 · Cited by 46
“In particular, it follows by [3][Chapter 13] and by the Claim in Section 3 that the degrees of the polynomials will be m and the coefficient size will be O(L+ log n)m.”
BackgroundInfluentialFixed points of the EM algorithm and nonnegative rank boundaries
Kubjas, K., Robeva, E., & Sturmfels, B. (2015) · The Annals of Statistics · doi:10.1214/14-aos1282 · Cited by 44
“gebraic. The boundary of any semialgebraic set is again semialgebraic. The formulas in Theorem 4.1 and Corollary 6.6 make this explicit. For more on semialgebraic sets and real algebraic geometry see [5]. ACKNOWLEDGEMENTS We thank Aldo Conca, Allen Knutson, Pierre-Jean Spaenlehauer, and Matteo Varbaro for helping us w…”
BackgroundInfluentialRefined Bounds on the Number of Connected Components of Sign Conditions on a Variety
Barone, S., & Basu, S. (2011) · Discrete & Computational Geometry · doi:10.1007/s00454-011-9391-3 · Cited by 42
Self-citationA Baby Step–Giant Step Roadmap Algorithm for General Algebraic Sets
Basu, S., Roy, M.-F., Din, M. S. E., et al. (2014) · Foundations of Computational Mathematics · doi:10.1007/s10208-014-9212-1 · Cited by 42
Self-citationOn the degree and half-degree principle for symmetric polynomials
Riener, C. (2011) · Journal of Pure and Applied Algebra · doi:10.1016/j.jpaa.2011.08.012 · Cited by 39
POLYNOMIAL-TIME COMPUTING OVER QUADRATIC MAPS I. SAMPLING IN REAL ALGEBRAIC SETSPreprint
Grigoriev, D., & Pasechnik, D. V. (2005) · Cited by 41
On the complexity of computing with planar algebraic curves
Kobel, A., & Sagraloff, M. (2014) · Journal of Complexity · doi:10.1016/j.jco.2014.08.002 · Cited by 36
Kavraki, L. E., & LaValle, S. M. (2008) · Springer eBooks · doi:10.1007/978-3-540-30301-5_6 · Cited by 73
An Elimination Method for Solving Bivariate Polynomial Systems: Eliminating the Usual Drawbacks
Berberich, E., Emeliyanenko, P., & Sagraloff, M. (2011) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611972917.4 · Cited by 41
Cell decomposition of almost smooth real algebraic surfaces
Besana, G. M., Rocco, S. D., Hauenstein, J. D., Sommese, A. J., & Wampler, C. W. (2012) · Numerical Algorithms · doi:10.1007/s11075-012-9646-y · Cited by 36
Alternating Projections on Nontangential Manifolds
Андерссон, Ф., & Carlsson, M. (2013) · Constructive Approximation · doi:10.1007/s00365-013-9213-3 · Cited by 38
“For more interesting examples in this direction, we refer to [4], Chap.”
Quadratic growth and critical point stability of semi-algebraic functions
Drusvyatskiy, D., & Ioffe, A. D. (2014) · Mathematical Programming · doi:10.1007/s10107-014-0820-y · Cited by 36
Din, M. S. E., & Schost, É. (2010) · Discrete & Computational Geometry · doi:10.1007/s00454-009-9239-2 · Cited by 41
Computing the first few Betti numbers of semi-algebraic sets in single exponential time
Basu, S. (2006) · Journal of Symbolic Computation · doi:10.1016/j.jsc.2006.07.001 · Cited by 37
“In order to do so, we will extend the ground field R to, R〈ε〉, the real closed field of algebraic Puiseux series in ε with coefficients in R (5).”
BackgroundMethodInfluentialSelf-citationErdős-Hajnal-type Results on Intersection Patterns of Geometric Objects
Fox, J., & Pach, J. (2008) · Bolyai Society mathematical studies · doi:10.1007/978-3-540-77200-2_4 · Cited by 36
APPROXIMATION OF DEFINABLE SETS BY COMPACT FAMILIES, AND UPPER BOUNDS ON HOMOTOPY AND HOMOLOGY
Gabrielov, A. M., & Vorobjov, N. (2007) · Cited by 36
Müller, S., & Regensburger, G. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-10515-4_22 · Cited by 40
“Mnëv’s universality theorem [38] theorem states that already for oriented matroids with rank d = 3, the realization space can be “arbitrarily complicated”; see [6] for a precise statement and [3] for semi-algebraic sets and algorithms.”
BackgroundColoring K k -free intersection graphs of geometric objects in the plane
Fox, J., & Pach, J. (2011) · European Journal of Combinatorics · doi:10.1016/j.ejc.2011.09.021 · Cited by 35
A Szemerédi–Trotter Type Theorem in R4
Zahl, J. (2015) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 35
Detecting similarity of rational plane curves
Alcázar, J. G., Hermoso, C., & Muntingh, G. (2014) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2014.03.013 · Cited by 34
A worst-case bound for topology computation of algebraic curves
Kerber, M., & Sagraloff, M. (2011) · Journal of Symbolic Computation · doi:10.1016/j.jsc.2011.11.001 · Cited by 34
Compiler support for selective page migration in NUMA architectures
Piccoli, G. G., Santos, H. N., Rodrigues, R. E., Ribeiro, C. P., Borin, E., & Pereira, F. M. Q. (2014) · International Conference on Parallel Architectures and Compilation Techniques (PACT) · doi:10.1145/2628071.2628077 · Cited by 45
“To simplify the formulas that we build in such fashion, we use the library [18] of symbolic manipulation. uses cylindrical algebraic decomposition [3] to solve the symbolic equations that we feed to it.”
MethodÁbrahám, E., Davenport, J. H., England, M., et al. (2020) · Journal of Logical and Algebraic Methods in Programming · doi:10.1016/j.jlamp.2020.100633 · Cited by 34
“The fragment of our interest, which excludes quantifier alternation, has lower theoretical complexity of singly exponential time (see for example [11]), however, currently no algorithms are implemented that realise this bound in general (see [12] for an analysis as to why).”
BackgroundSmoothing the gap between NP and ER
Erickson, J., van der Hoog, I., & Miltzow, T. (2020) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs46700.2020.00099 · Cited by 34
Qualitative Spatial Reasoning for Applications
Wolter, D., & Wallgrün, J. O. (2012) · IGI Global eBooks · doi:10.4018/978-1-4666-2038-4.ch099 · Cited by 34
Betti Numbers of Semialgebraic Sets Defined by Quantifier-Free Formulae
Gabrielov, A. M., & Vorobjov, N. (2004) · Discrete & Computational Geometry · doi:10.1007/s00454-004-1105-7 · Cited by 34
“where k is the number of distinct polynomials in the defining formula (this is a relaxed form of Basu’s bound, for a more precise description see [1, 2].”
BackgroundOn the complexity of minimizing probabilistic and quantum automata
Mateus, P., Qiu, D., & Li, L. (2012) · Information and Computation · doi:10.1016/j.ic.2012.07.002 · Cited by 32
On the topology of planar algebraic curves
Cheng, J.-S., Lazard, S., Peñaranda, L., et al. (2009) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/1542362.1542424 · Cited by 33
Validating numerical semidefinite programming solvers for polynomial invariants
Roux, P., Voronin, Y.-L., & Sankaranarayanan, S. (2017) · Formal Methods in System Design · doi:10.1007/s10703-017-0302-y · Cited by 33
“They also represent a rich class of constraints with a decidable entailment checking problem [9].”
BackgroundMethodDin, M. S. E., & Schost, É. (2018) · HAL (Le Centre pour la Communication Scientifique Directe) · doi:10.1016/j.jsc.2017.08.001 · Cited by 33
Parametric Markov chains: PCTL complexity and fraction-free Gaussian elimination
Christel Baier, A., Hensel, C., Hutschenreiter, L., Junges, S., Katoen, J.-P., & Klein, J. (2019) · Information and Computation · doi:10.1016/j.ic.2019.104504 · Cited by 32
A Szemerédi–Trotter Type Theorem in $$\mathbb {R}^4$$
Zahl, J. (2015) · Discrete & Computational Geometry · doi:10.1007/s00454-015-9717-7 · Cited by 56
“Definitions and standard results about real algebraic varieties can be found in [3,4].”
BackgroundDistinct Distances on Algebraic Curves in the Plane
Pach, J., & de Zeeuw, F. (2016) · Combinatorics Probability Computing · doi:10.1017/s0963548316000225 · Cited by 32
Solving bivariate systems using Rational Univariate Representations
Bouzidi, Y., Lazard, S., Moroz, G., et al. (2016) · Journal of Complexity · doi:10.1016/j.jco.2016.07.002 · Cited by 32
Truth Table Invariant Cylindrical Algebraic Decomposition by Regular Chains
Bradford, R., Chen, C., Davenport, J. H., et al. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-10515-4_4 · Cited by 31
“While for some applications there now exist algorithms with better complexity (see for example [5]), CAD implementations remain the best general purpose approach for many.”
BackgroundImproving the Use of Equational Constraints in Cylindrical Algebraic Decomposition
England, M., Bradford, R., & Davenport, J. H. (2015) · ACM International Symposium on Symbolic and Algebraic Computation (ISSAC) · doi:10.1145/2755996.2756678 · Cited by 31
Reaching generalized critical values of a polynomial
Jelonek, Z., & Kurdyka, K. (2013) · Mathematische Zeitschrift · doi:10.1007/s00209-013-1213-2 · Cited by 28
The phase limit set of a variety
Nisse, M., & Sottile, F. (2013) · Algebra & Number Theory · doi:10.2140/ant.2013.7.339 · Cited by 31
“Thus, coamoebae, as they are the image of a real algebraic subset of the real algebraic variety TN under the real algebraic map arg, are semialgebraic subsets of UN [Basu et al. 2006].”
BackgroundDifferential Elimination and Biological Modelling
Boulier, F. (2007) · De Gruyter eBooks · doi:10.1515/9783110922752.109 · Cited by 31
“By Descartes rule of sign [3], the number of positive real roots is at most one.”
BackgroundStabbing simplices by points and flats
Bukh, B., & Nivasch, G. (2009) · Cited by 31
Different Bounds on the Different Betti Numbers of Semi-Algebraic Sets
Basu, S. (2003) · Discrete & Computational Geometry · doi:10.1007/s00454-003-2922-9 · Cited by 33
Self-citationExact symbolic–numeric computation of planar algebraic curves
Berberich, E., Emeliyanenko, P., Kobel, A., et al. (2013) · Theoretical Computer Science · doi:10.1016/j.tcs.2013.04.014 · Cited by 30
“As mentioned above, the resultant polynomials have the following important property (see [24] for a proof):”
BackgroundInfluentialAllamigeon, X., Gaubert, S., & Skomra, M. (2020) · Discrete & Computational Geometry · doi:10.1007/s00454-020-00176-1 · Cited by 37
The Art Gallery Problem is ∃ℝ-complete
Abrahamsen, M., Adamaszek, A., & Miltzow, T. (2021) · Journal of the ACM · doi:10.1145/3486220 · Cited by 30
Stabbing Simplices by Points and Flats
Bukh, B., Matoušek, J., & Nivasch, G. (2008) · Discrete & Computational Geometry · doi:10.1007/s00454-008-9124-4 · Cited by 30
On the minimum of a positive polynomial over the standard simplex
Jeronimo, G., & Perrucci, D. (2010) · Journal of Symbolic Computation · doi:10.1016/j.jsc.2010.01.001 · Cited by 29
Huang, Q., Li, C., & Song, X. (2022) · Construction and Building Materials · doi:10.1016/j.conbuildmat.2022.126922 · Cited by 28
Basu, S., & Sombra, M. (2015) · Discrete & Computational Geometry · doi:10.1007/s00454-015-9736-4 · Cited by 30
Self-citationIntrinsic complexity estimates in polynomial optimization
Bank, B., Giusti, M., Heintz, J., et al. (2014) · Journal of Complexity · doi:10.1016/j.jco.2014.02.005 · Cited by 28
“But, at least for global optimization, one can do much better with an sd sequential time bound (see [8], Algorithm 14.”
BackgroundSalzman, O., Hemmer, M., & Dan Halperin, C. (2014) · IEEE Transactions on Automation Science and Engineering · doi:10.1109/tase.2014.2331983 · Cited by 34
“C2 A pair of surfaces chosen uniformly and independently3 at random from M intersect with significant probability.”
BackgroundCOMPUTING NERON–SEVERI GROUPS AND CYCLE CLASS GROUPS
Poonen, B., Testa, D., Ronald, et al. (2013) · Cited by 28
On the boolean complexity of real root refinement
Pan, V. Y., & Tsigaridas, E. (2013) · International Symposium on Symbolic and Algebraic Computation · doi:10.1145/2465506.2465938 · Cited by 27
Metadata
- Authors
- Basu, S., Pollack, R., & Roy, M.-F.
- Affiliations
- Georgia Institute of Technology (US)
- Courant Institute of Mathematical Sciences (US)
- Institut de recherche mathématique de Rennes (FR)
- Venue
- Algorithms and computation in mathematics
- Publisher
- Springer Berlin Heidelberg
- Published
- 2006
- ISSN
- 1431-1550 (ISSN-L)
- OpenAlex
- W4255213956
- Cited by
- 868
- References
- 3
- Citations by year
- 2026: 27 · 2025: 37 · 2024: 65 · 2023: 52 · 2022: 58 · 2021: 54 · 2020: 48 · 2019: 46 · 2018: 48 · 2017: 37 · 2016: 46 · 2015: 54 · 2014: 54 · 2013: 35 · 2012: 40
- FWCI
- 9.06
- Type
- book
- Language
- en
- Open access
- closed
- Licence
- www.springer.com/tdm (tdm)
- Locations
- Algorithms and computation in mathematics (publishedVersion)
- CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
- Digital Access to Libraries (Université catholique de Louvain (UCL), l'Université de Namur (UNamur) and the Université Saint-Louis (USL-B)) (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Polynomial and algebraic computation
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Mathematics › Geometry and Topology › Algebraic Geometry and Number Theory
- Keywords
- real algebraic geometry, real root counting, polynomial systems, polynomial inequalities, global optimization, existence of solutions, computational complexity
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.