Hardness of Approximation for 2 → 4 Norms through Quantum Reductions
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