### Abstract

We study the ε-rank of a real matrix A, defined for any ε > 0 as the minimum rank over matrices that approximate every entry of A to within an additive ε. This parameter is connected to other notions of approximate rank and is motivated by problems from various topics including communication complexity, combinatorial optimization, game theory, computational geometry and learning theory. Here we give bounds on the ε-rank and use them for algorithmic applications. Our main algorithmic results are (a) polynomial-time additive approximation schemes for Nash equilibria for 2-player games when the payoff matrices are positive semidefinite or have logarithmic rank and (b) an additive PTAS for the densest subgraph problem for similar classes of weighted graphs. We use combinatorial, geometric and spectral techniques; our main new tool is an algorithm for efficiently covering a convex body with translates of another convex body.

Original language | English (US) |
---|---|

Title of host publication | STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing |

Pages | 675-684 |

Number of pages | 10 |

DOIs | |

State | Published - Jul 11 2013 |

Externally published | Yes |

Event | 45th Annual ACM Symposium on Theory of Computing, STOC 2013 - Palo Alto, CA, United States Duration: Jun 1 2013 → Jun 4 2013 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | 45th Annual ACM Symposium on Theory of Computing, STOC 2013 |
---|---|

Country | United States |

City | Palo Alto, CA |

Period | 6/1/13 → 6/4/13 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

- Approximate rank
- Convex body
- Covering number
- Nash equilibria

## Fingerprint Dive into the research topics of 'The approximate rank of a matrix and its algorithmic applications'. Together they form a unique fingerprint.

## Cite this

*STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing*(pp. 675-684). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/2488608.2488694