{"id":"arxiv/2605.25303","url":"https://arxiv.org/abs/2605.25303","tags":["cs.DS","cs.LG","math.ST","stat.ML"],"score":0,"title":"Algorithms with Polynomially-Improved Approximation Factors for the $2 \\rightarrow q$ Norm, and Applications","domain":"cs.DS","source":"arxiv","authors":["Samuel B. Hopkins","Stefan Tiegel"],"reviews":0,"subject":"cs.DS","summary":"The $2 \\rightarrow q$ norm of a matrix $X \\in \\mathbb{R}^{n \\times d}$ is defined as $\\lVert X \\rVert_{2 \\rightarrow q} = \\sup_{\\lVert v \\rVert_2 = 1} \\lVert Xv \\rVert_q$. We give polynomial-time multiplicative approximation algorithms for this norm when $q > 2$ (i.e. in the hypercontractive setting). This problem either directly captures or is closely related to long-standing open problems in combinatorial optimization and hardness of approximation (e.g. Small Set Expansion), quantum information (e.g. Best Separable State), and algorithmic statistics. Very little is known about what…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-24","reactions":{}}