Sparse covers for sums of indicators

• 成果类型: Article
• 署名作者: Daskalakis, Constantinos; Papadimitriou, Christos
• 署名单位: Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); University of California System; University of California Berkeley
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-014-0582-8
• 发表日期: 2015
• 页码: 679-705
• 关键词: binomial approximation; Poisson approximation; games

摘要

For all , we show that the set of Poisson Binomial distributions on variables admits a proper -cover in total variation distance of size , 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.