18 citations · 42 across the 9 of their papers we have counts for
5 papers · 1 filter
Complexity Aspects of Fundamental Questions in Polynomial Optimization
Jeffrey Zhang
In this thesis, we settle the computational complexity of some fundamental questions in polynomial optimization. These include the questions of (i) finding a local minimum, (ii) te…
Complexity aspects of local minima and related notions
Amir Ali Ahmadi, Jeffrey Zhang
We consider the notions of (i) critical points, (ii) second-order points, (iii) local minima, and (iv) strict local minima for multivariate polynomials. For each type of point, and…
On the complexity of finding a local minimizer of a quadratic function over a polytope
Amir Ali Ahmadi, Jeffrey Zhang
We show that unless P=NP, there cannot be a polynomial-time algorithm that finds a point within Euclidean distance (for any constant ) of a local minimizer of an …
On the Complexity of Testing Attainment of the Optimal Value in Nonlinear Optimization
Amir Ali Ahmadi, Jeffrey Zhang
We prove that unless P=NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can test whether the optimal value of a nonlinear optimization problem wh…
Semidefinite Programming and Nash Equilibria in Bimatrix Games
Amir Ali Ahmadi, Jeffrey Zhang
We explore the power of semidefinite programming (SDP) for finding additive -approximate Nash equilibria in bimatrix games. We introduce an SDP relaxation for a quadratic…