Inapproximability of Matrix p q Norms

DOI10.1137/18M1233418MaRDI QIDQ5885598zbMATH OpenOpenAlexFDO

Authors Vijay V. S. P. Bhattiprolu, Mrinalkanti Ghosh, Euiwoong Lee, Madhur Tulsiani, 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

continuous optimizationinapproximabilityoperator norms

Mathematics Subject Classification ID

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

Recommendations

• Approximability of \(p\rightarrow q\) matrix norms: generalized Krivine rounding and hypercontractive hardness
• Matrix p-norms are NP-hard to approximate if p1,2,
• scientific article; zbMATH DE number 6783411
• Hypercontractivity, sum-of-squares proofs, and their applications
• Tight hardness of the non-commutative Grothendieck problem

Cites work

• A fast and simple randomized parallel algorithm for the maximal independent set problem
• An application of Fourier methods to the problem of sharpening the Berry-Esseen inequality
• Bypassing UGC from some optimal geometric inapproximability results
• Graph expansion and the unique games conjecture
• Grothendieck-type inequalities in combinatorial optimization
• Grothendieck’s Theorem, past and present
• High-dimensional \(p\)-norms
• scientific article; zbMATH DE number 3124239 (Why is no real title available?)
• scientific article; zbMATH DE number 4078003 (Why is no real title available?)
• scientific article; zbMATH DE number 3176196 (Why is no real title available?)
• scientific article; zbMATH DE number 3571163 (Why is no real title available?)
• scientific article; zbMATH DE number 2206777 (Why is no real title available?)
• scientific article; zbMATH DE number 6783411 (Why is no real title available?)
• Hypercontractivity, sum-of-squares proofs, and their applications
• Linear Equations Modulo 2 and the L₁ Diameter of Convex Bodies
• Quadratic forms on graphs
• SDP gaps and UGC-hardness for max-cut-gain
• Semidefinite relaxation and nonconvex quadratic optimization
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Testing product states, quantum Merlin-Arthur games and tensor optimization
• The best constants in the Khintchine inequality
• The Grothendieck constant is strictly smaller than Krivine's bound
• The UGC hardness threshold of the \(L_{p}\) Grothendieck problem
• Towards computing the Grothendieck constant
• Two observations regarding embedding subsets of Euclidean spaces in normed spaces

Cited in

(3)

• scientific article; zbMATH DE number 6783411 (Why is no real title available?)
• The generalized matrix norm problem
• Estimating the matrix p q norm

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5885598)