Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness

DOI10.1137/1.9781611975482.83zbMath1431.68041OpenAlexW4235546643MaRDI QIDQ5236267

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

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611975482.83

Mathematics Subject Classification ID

Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (2)

A note on the Hausdorff distance between norm balls and their linear maps ⋮ Mean estimation with sub-Gaussian rates in polynomial time

This page was built for publication: Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness