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
This publication is archived. It is kept only for reference purposes, so it is no longer being updated and may not meet accessibility standards. If you need this content in a different format, please email webteam@eecs.berkeley.edu.
http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/Archive/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