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

**Lek-Heng Lim**

3-tensors as the boundary of tractability

**Coauthor: Christopher Hillar**

**Abstract:**

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"** [...]