Approximating sparse binary matrices in the cut-norm

DOI10.1016/J.LAA.2015.08.024MaRDI QIDQ498332zbMATH OpenOpenAlexFDO

Authors Noga Alon

Publication date 28 September 2015

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.laa.2015.08.024

zbMATH Keywords

low rank approximationcutnorm

Mathematics Subject Classification ID

Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60)

Recommendations

• An efficient sparse regularity concept
• Approximating the Cut-Norm via Grothendieck's Inequality
• An efficient sparse regularity concept
• Approximating the cut-norm via Grothendieck's inequality
• Sampling from large matrices

Cites work

• Equilateral sets in \(l_p^n\)
• On the best constants in the Khinchin inequality
• Perturbed Identity Matrices Have High Rank: Proof and Applications
• Quick approximation to matrices and applications
• Random sampling and approximation of MAX-CSPs
• The Hadamard Operator Norm of a Circulant and Applications
• The approximate rank of a matrix and its algorithmic applications
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(5)

• An ensemble of high rank matrices arising from tournaments
• An efficient sparse regularity concept
• An efficient sparse regularity concept
• Ultimate data hiding in quantum mechanics and beyond
• Low-weight halfspaces for sparse boolean vectors

This page was built for publication: Approximating sparse binary matrices in the cut-norm

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