The approximate rank of a matrix and its algorithmic applications

DOI10.1145/2488608.2488694zbMath1293.68136OpenAlexW2010106582MaRDI QIDQ5495838

Troy Lee, Adi Shraibman, Noga Alon, Santosh Vempala

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2488608.2488694

zbMATH Keywords

Nash equilibriaconvex bodycovering numberapproximate rank

Mathematics Subject Classification ID

Related Items (14)

Linear-size universal discretization of geometric center-based problems in fixed dimensions ⋮ Functional norms, condition numbers and numerical algorithms in algebraic geometry ⋮ Matrix and tensor rigidity and \(L_p\)-approximation ⋮ Constant Rank Two-Player Games are PPAD-hard ⋮ Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem ⋮ Around the log-rank conjecture ⋮ Kolmogorov width and approximate rank ⋮ Theorems of Carathéodory, Helly, and Tverberg without dimension ⋮ On the distance to low-rank matrices in the maximum norm ⋮ Regularity lemmas in a Banach space setting ⋮ Approximating sparse binary matrices in the cut-norm ⋮ Unnamed Item ⋮ Why Are Big Data Matrices Approximately Low Rank? ⋮ Upper bounds on communication in terms of approximate rank

This page was built for publication: The approximate rank of a matrix and its algorithmic applications