Approximating sparse binary matrices in the cut-norm

DOI10.1016/J.LAA.2015.08.024zbMATH Open1327.15044OpenAlexW1786358965MaRDI QIDQ498332FDOQ498332

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

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

zbMATH Keywords

low rank approximationcutnorm

Mathematics Subject Classification ID

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

Cites Work

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

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)