The Computational Complexity of Duality

R. T. Rockafellar, Convex Analysis , Princeton Mathematical Series, 28

1970

Earlier work this paper cites.

D. B. Yudin and A. S. Nemirovski, “Informational complexity and efficient methods for the solution of convex extremal problems,” Matekon , 13

Original

1977

Earlier work this paper cites.

J. Bourgain and V. Milman, “New volume ratio properties for convex symmetric bodies in ℝ n \mathbb{R}^{n} ,” Invent. Math. , 88

1987

Earlier work this paper cites.

K. G. Murty and S. N. Kabadi, “Some NP-complete problems in quadratic and nonlinear programming,” Math. Programming , 39

1987

Earlier work this paper cites.

M. Dyer, A. Frieze, and R. Kannan, “A random polynomial-time algorithm for approximating the volume of convex bodies,” J. Assoc. Comput. Mach. , 38

1991

Earlier work this paper cites.

M. Grötschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization , 2nd Ed., Algorithms and Combinatorics, 2

1993

Cited alongside, same era.

L. Gurvits, “Classical deterministic complexity of Edmonds problem and quantum entanglement,” Proc. ACM Symp. Theory Comput. (STOC), 35

2003

Cited alongside, same era.

S. Artstein-Avidan and V. Milman, “The concept of duality in convex analysis, and the characterization of the Legendre transform,” Ann. Math. , 169

2009

Cited alongside, same era.

J. W. Helton and J. Nie, “Semidefinite representation of convex sets,” Math. Program

2010

Cited alongside, same era.

C. J. Hillar and L.-H. Lim, “Most tensor problems are NP-hard,” J. Assoc. Comput. Mach. , 60

2013

Later among the works it cites.

P. J. C. Dickinson and L. Gijben, “On the computational complexity of membership problems for the completely positive cone and its dual,” Comput. Optim. Appl. , 57

2014

Later among the works it cites.

S. Friedland and L.-H. Lim, “Nuclear norm of higher-order tensors,” preprint , (2016), http://arxiv.org/abs/1410.6072

Original

2016

Closest in time.

B. Jiang, Z. Li, and S. Zhang, “On cones of nonnegative quartic forms,” Found. Comput. Math. , (2016), to appear

2016

Closest in time.