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

2-person games (91A05) Determinants, permanents, traces, other special matrix functions (15A15) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Signed and weighted graphs (05C22)

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