REVIEW
Matrix P-norms are NP-hard to approximate if p neq 1,2,infty
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Matrix P-norms are NP-hard to approximate if p neq 1,2,infty
classification
cs.CC
keywords
inftyalgorithmmatrixpolynomial-timeprecisionrationalrelativethere
read the original abstract
We show that for any rational p \in [1,\infty) except p = 1, 2, unless P = NP, there is no polynomial-time algorithm for approximating the matrix p-norm to arbitrary relative precision. We also show that for any rational p\in [1,\infty) including p = 1, 2, unless P = NP, there is no polynomial-time algorithm approximates the \infty, p mixed norm to some fixed relative precision.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.