Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms

DOI10.1137/18M1233418OpenAlexW4320487114MaRDI QIDQ5885598

Euiwoong Lee, Madhur Tulsiani, Mrinalkanti Ghosh, Vijay V. S. P. Bhattiprolu, Venkatesan Guruswami

Publication date: 4 April 2023

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1802.07425

zbMATH Keywords

operator normsinapproximabilitycontinuous optimization

Mathematics Subject Classification ID

Computer science (68-XX) Functional analysis (46-XX) Operations research, mathematical programming (90-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Two observations regarding embedding subsets of Euclidean spaces in normed spaces
• Graph expansion and the unique games conjecture
• Grothendieck-Type Inequalities in Combinatorial Optimization
• The UGC Hardness Threshold of the L_p Grothendieck Problem
• Linear Equations Modulo 2 and the $L_1$ Diameter of Convex Bodies
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• The best constants in the Khintchine inequality
• Semidefinite relaxation and nonconvex quadratic optimization
• Bypassing UGC from Some Optimal Geometric Inapproximability Results
• High-Dimensional $$p$$-Norms
• Grothendieck’s Theorem, past and present
• Testing Product States, Quantum Merlin-Arthur Games and Tensor Optimization
• THE GROTHENDIECK CONSTANT IS STRICTLY SMALLER THAN KRIVINE’S BOUND
• Hypercontractivity, sum-of-squares proofs, and their applications
• An application of Fourier methods to the problem of sharpening the Berry-Esseen inequality
• Quadratic forms on graphs

This page was built for publication: Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms