Sparse covers for sums of indicators
For all n, ε > 0), we show that the set of Poisson Binomial distributions on n variables admits a proper ε-cover in total variation distance of size n[superscript 2] + n · (1/ε)[superscript O(log[superscript 2] (1/ε)), which can also be computed in polynomial time. We discuss the implications of...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2015
|
| Online Access: | http://hdl.handle.net/1721.1/99971 https://orcid.org/0000-0002-5451-0490 |
| _version_ | 1826207822257324032 |
|---|---|
| author | Papadimitriou, Christos Daskalakis, Konstantinos |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Papadimitriou, Christos Daskalakis, Konstantinos |
| author_sort | Papadimitriou, Christos |
| collection | MIT |
| description | For all n, ε > 0), we show that the set of Poisson Binomial distributions on n variables admits a proper ε-cover in total variation distance of size n[superscript 2] + n · (1/ε)[superscript O(log[superscript 2] (1/ε)), which can also be computed in polynomial time. We discuss the implications of our construction for approximation algorithms and the computation of approximate Nash equilibria in anonymous games. |
| first_indexed | 2024-09-23T13:55:30Z |
| format | Article |
| id | mit-1721.1/99971 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:55:30Z |
| publishDate | 2015 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/999712022-09-28T17:05:15Z Sparse covers for sums of indicators Papadimitriou, Christos Daskalakis, Konstantinos Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Daskalakis, Konstantinos For all n, ε > 0), we show that the set of Poisson Binomial distributions on n variables admits a proper ε-cover in total variation distance of size n[superscript 2] + n · (1/ε)[superscript O(log[superscript 2] (1/ε)), which can also be computed in polynomial time. We discuss the implications of our construction for approximation algorithms and the computation of approximate Nash equilibria in anonymous games. Alfred P. Sloan Foundation (Fellowship) Microsoft Research (Faculty Fellowship) National Science Foundation (U.S.) (CAREER Award CCF-0953960) National Science Foundation (U.S.) (Award CCF-1101491) 2015-11-20T18:44:55Z 2015-11-20T18:44:55Z 2014-11 2014-10 Article http://purl.org/eprint/type/JournalArticle 0178-8051 1432-2064 http://hdl.handle.net/1721.1/99971 Daskalakis, Constantinos, and Christos Papadimitriou. “Sparse Covers for Sums of Indicators.” Probab. Theory Relat. Fields 162, no. 3–4 (November 2, 2014): 679–705. https://orcid.org/0000-0002-5451-0490 en_US http://dx.doi.org/10.1007/s00440-014-0582-8 Probability Theory and Related Fields Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer-Verlag arXiv |
| spellingShingle | Papadimitriou, Christos Daskalakis, Konstantinos Sparse covers for sums of indicators |
| title | Sparse covers for sums of indicators |
| title_full | Sparse covers for sums of indicators |
| title_fullStr | Sparse covers for sums of indicators |
| title_full_unstemmed | Sparse covers for sums of indicators |
| title_short | Sparse covers for sums of indicators |
| title_sort | sparse covers for sums of indicators |
| url | http://hdl.handle.net/1721.1/99971 https://orcid.org/0000-0002-5451-0490 |
| work_keys_str_mv | AT papadimitriouchristos sparsecoversforsumsofindicators AT daskalakiskonstantinos sparsecoversforsumsofindicators |