NP-hardness of Nuclear Norms for Tensors
summary
Proves that computing tensor nuclear norms and deciding weak membership of the nuclear-ball are NP-hard to approximate by reducing from graph clique number; constructs nonnegative symmetric tensors whose spectral norm equals 1 − 1/κ(G) and uses duality to transfer hardness to the nuclear norm. Shows bipartite density matrix is separable exactly when its nuclear norm equals one (nuclear norm equals one iff separable), relies on classical Turing reductions with rational inputs, and notes alternating heuristics only give local optima.
AI-written summary · about
chapters (5)
- 0:00Start
- 6:04Spectral and Nuclear Norm for Matrices
- 12:31Minimal characterization of matrix nuclear norm
- 24:494-tensors and bi-partite density matrices
- 37:56Unit ball of a norm
related talks
01h 57mFun with Lattices
27mSparsity and Privacy in Distributed Matrix Multiplication
30mFamilies of Anticommuting Matrices and the Sum of Squares Problem
21mDecision and Complexity of Dolev-Yao Hyperproperties
01h 06mCompiled Nonlocal Games: From CHSH to BQP Verification
31mDistance-Aware OT with Application to Fuzzy PSI
01h 00mQuantum Commitments and Black Hole Radiation Decoding
14mGuarding the Privacy of Label-Only Access to Neural Network Classifiers via Formal(…)