First poly-time 2 to q norm approximation algorithms beating the d^{1/4} baseline by polynomial factors (d^{1/8} for q=4) plus SOS certificates enabling improved robust mean/covariance estimation and clustering under q-moment bounds.
and Naor, A
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
abstract
We present several polynomial- and quasipolynomial-time approximation schemes for a large class of generalized operator norms. Special cases include the $2\rightarrow q$ norm of matrices for $q>2$, the support function of the set of separable quantum states, finding the least noisy output of entanglement-breaking quantum channels, and approximating the injective tensor norm for a map between two Banach spaces whose factorization norm through $\ell_1^n$ is bounded. These reproduce and in some cases improve upon the performance of previous algorithms by Brand\~ao-Christandl-Yard and followup work, which were based on the Sum-of-Squares hierarchy and whose analysis used techniques from quantum information such as the monogamy principle of entanglement. Our algorithms, by contrast, are based on brute force enumeration over carefully chosen covering nets. These have the advantage of using less memory, having much simpler proofs and giving new geometric insights into the problem. Net-based algorithms for similar problems were also presented by Shi-Wu and Barak-Kelner-Steurer, but in each case with a run-time that is exponential in the rank of some matrix. We achieve polynomial or quasipolynomial runtimes by using the much smaller nets that exist in $\ell_1$ spaces. This principle has been used in learning theory, where it is known as Maurey's empirical method.
years
2026 3verdicts
UNVERDICTED 3representative citing papers
StoqMA(2) contains NP with Õ(√n)-qubit proofs and completeness error 2^{-polylog(n)}, is contained in EXP, and satisfies StoqMA(k)=StoqMA(2) for k≥2 when completeness error is negligible.
A framework using reverse detection-estimation gaps proves that low-degree algorithms incur at least p^{d/4-1/2}/polylog(p) distortion when approximating the spectral norm of order-d symmetric tensors, matching upper bounds up to logs under the low-degree conjecture.
citing papers explorer
-
Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications
First poly-time 2 to q norm approximation algorithms beating the d^{1/4} baseline by polynomial factors (d^{1/8} for q=4) plus SOS certificates enabling improved robust mean/covariance estimation and clustering under q-moment bounds.
-
Unentangled stoquastic Merlin-Arthur proof systems: the power of unentanglement without destructive interference
StoqMA(2) contains NP with Õ(√n)-qubit proofs and completeness error 2^{-polylog(n)}, is contained in EXP, and satisfies StoqMA(k)=StoqMA(2) for k≥2 when completeness error is negligible.
-
A Framework for Computational Lower Bounds in Nontrivial Norm Approximation
A framework using reverse detection-estimation gaps proves that low-degree algorithms incur at least p^{d/4-1/2}/polylog(p) distortion when approximating the spectral norm of order-d symmetric tensors, matching upper bounds up to logs under the low-degree conjecture.