Rohit Agarwal and Axel Li and Anthony Maltsev and Anirba Sarkar

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2023-236

November 20, 2023

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-236.pdf

We study the computational complexity of approximating 2 → 4 linear operator norm, defined as ∥A∥2→4 = maxf̸ =0(∥Af ∥4/∥f ∥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].

---

BibTeX citation:

@techreport{Agarwal:EECS-2023-236,
    Author= {Agarwal, Rohit and Li, Axel and Maltsev, Anthony and Sarkar, Anirba},
    Title= {Hardness of Approximation for 2 → 4 Norms through Quantum Reductions},
    Year= {2023},
    Month= {Nov},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-236.html},
    Number= {UCB/EECS-2023-236},
    Abstract= {We study the computational complexity of approximating 2 → 4 linear operator norm, defined as ∥A∥2→4 = maxf̸ =0(∥Af ∥4/∥f ∥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].},
}

EndNote citation:

%0 Report
%A Agarwal, Rohit 
%A Li, Axel 
%A Maltsev, Anthony 
%A Sarkar, Anirba 
%T Hardness of Approximation for 2 → 4 Norms through Quantum Reductions
%I EECS Department, University of California, Berkeley
%D 2023
%8 November 20
%@ UCB/EECS-2023-236
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-236.html
%F Agarwal:EECS-2023-236