Monday, 13:45 - 14:10 h, Room: H 0112


Lek-Heng Lim
3-tensors as the boundary of tractability

Coauthor: Christopher Hillar


Why do problems in numerical computing become intractable as they transition from linear to nonlinear or convex to nonconvex? We shall argue that 3-tensor problems form the boundary separating the tractability of linear algebra and convex optimization from the intractability of polynomial algebra and nonconvex optimization - 3-tensor analogues of many efficiently computable matrix problems are NP-hard. Our list includes: determining the feasibility of a system of bilinear equations, deciding whether a 3-tensor possesses a given eigenvalue, singular value, or spectral norm; approximating an eigenvalue, eigenvector, singular vector, or spectral norm; determining the rank or a best rank-1 approximation to a 3-tensor. Additionally, some of these problems have no polynomial time approximation schemes, some are undecidable over Q, and at least one enumerative version is #P-complete. Restricting these problems to symmetric 3-tensors does not alleviate their NP-hardness.


Talk 2 of the invited session Mon.2.H 0112
"Structures, complexities, and eigenvalues of tensor forms and polynomial functions" [...]
Cluster 16
"Nonlinear programming" [...]


  Payday Loans Wisconsin. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.