Fetching the paper…
Reading the bibliography…
We show that unless P=NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can decide whether a multivariate polynomial of degree four (or higher even degree) is globally convex.
A decision method for elementary algebra and geometry
A. Tarski · 1951
Earlier work this paper cites.
A new decision method for elementary algebra
A. Seidenberg · 1954
Earlier work this paper cites.
Quasi-concave programming
K. J. Arrow and A. C. Enthoven · 1961
Earlier work this paper cites.
Pseudo-convex functions
O. L. Mangasarian · 1965
Earlier work this paper cites.
Nonlinear Programming
O. L. Mangasarian · 1969
Earlier work this paper cites.
On pseudo-convex functions of nonnegative variables
R. W. Cottle and J. A. Ferland · 1971
Earlier work this paper cites.
Second order conditions for pseudo-convex functions
P. Mereau and J. G. Paquet · 1974
Earlier work this paper cites.
Positive semidefinite biquadratic forms
M. D. Choi · 1975
Earlier work this paper cites.
Testing and imposing monotonicity, convexity and quasiconvexity constraints
L. J. Lau · 1978
Earlier work this paper cites.
Computers and Intractability
M. R. Garey and D. S. Johnson · 1979
Earlier work this paper cites.
Matrix-theoretic criteria for the quasiconvexity of twice continuously differentiable functions
J. A. Ferland · 1981
Earlier work this paper cites.
Criteria for quasiconvexity and pseudoconvexity: relationships and comparisons
J. P. Crouzeix and J. A. Ferland · 1982
Earlier work this paper cites.
Some NP-complete problems in quadratic and nonlinear programming
K. G. Murty and S. N. Kabadi · 1987
Earlier work this paper cites.
Some algebraic and geometric computations in PSPACE
J. Canny · 1988
Earlier work this paper cites.
Open questions in complexity theory for numerical optimization
P. M. Pardalos and S. A. Vavasis · 1992
Cited alongside, same era.
Complexity in Numerical Optimization
P. M. Pardalos, editor · 1993
Cited alongside, same era.
Lagrange multipliers and optimality
R. T. Rockafellar · 1993
Cited alongside, same era.
Matrix Analysis
R. A. Horn and C. R. Johnson · 1995
Cited alongside, same era.
On the difficulty of deciding the convexity of polynomials over simplexes
B. Guo · 1996
Cited alongside, same era.
A survey of computational complexity results in systems and control
V. D. Blondel and J. N. Tsitsiklis · 2000
Cited alongside, same era.
Automated analysis of convexity properties of nonlinear programs
Nonlinear Programming
M. S. Bazaraa, H. D. Sherali, and C. M. Shetty · 2006
Later among the works it cites.
Establishing convexity of polynomial Lyapunov functions and their sublevel sets
G. Chesi and Y. S. Hung · 2008
Later among the works it cites.
The complexity of optimizing over a simplex, hypercube or sphere: a short survey
E. de Klerk · 2008
Later among the works it cites.
Convexity in semialgebraic geometry and polynomial optimization
J. B. Lasserre · 2008
Later among the works it cites.
Representation of nonnegative convex polynomials
J. B. Lasserre · 2008
Later among the works it cites.
A convex polynomial that is not sos-convex
A. A. Ahmadi and P. A. Parrilo · 2009
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
C. A. R. Crusius · 2002
Cited alongside, same era.
Distinguishing separable and entangled states
A. C. Doherty, P. A. Parrilo, and F. M. Spedalieri · 2002
Cited alongside, same era.
Classical deterministic complexity of Edmonds’ problem and quantum entanglement
L. Gurvits · 2003
Cited alongside, same era.
Minimizing polynomial functions
P. A. Parrilo and B. Sturmfels · 2003
Cited alongside, same era.
Convex Optimization
S. Boyd and L. Vandenberghe · 2004
Cited alongside, same era.
Testing geometric convexity
L. Rademacher and S. Vempala · 2004
Cited alongside, same era.
A positive definite polynomial Hessian that does not factor
A. A. Ahmadi and P. A. Parrilo · 2009
Later among the works it cites.
Biquadratic optimization over unit spheres and semidefinite programming relaxations
C. Ling, J. Nie, L. Qi, and Y. Ye · 2009
Later among the works it cites.
Polynomial matrix inequality and semidefinite representation
J. Nie · 2009
Later among the works it cites.
On the equivalence of algebraic conditions for convexity and quasiconvexity of polynomials
A. A. Ahmadi and P. A. Parrilo · 2010
Closest in time.
CVX: Matlab software for disciplined convex programming, version 1.21
M. Grant and S. Boyd · 2010
Closest in time.
Semidefinite representation of convex sets
J. W. Helton and J. Nie · 2010
Closest in time.
Certificates of convexity for basic semi-algebraic sets
J. B. Lasserre · 2010
Closest in time.