PDF

Description

We study the computational complexity of approximating 2 → 4 linear operator norm, defined as ∥A2→4 = maxƒ≠0(∥Aƒ∥4/∥ƒ∥2) We explore the problem of multiplicatively approximating to such a norm to a constant factor. We present the previous results in the area, share our attempt to give a new NP-hardness proof, and discuss applications to other problems, such as Khot’s Unique Games Conjecture [7].

Details

Files

Statistics

from
to
Export
Download Full History