Constructive Proofs of Concentration Bounds

Russell Impagliazzo, Valentine Kabanets
http://eccc.hpi-web.de/report/2010/072/

さて，離散数学における確率論的手法の分野において「constructive proof」が最近注目されている気がする．その端緒はMoserによるLovasz Local Lemmaのconstructive proof (とそれのMoser & Tardosによる一般化) だと思うけども，この論文はChernoffの不等式のconstructive proofをしていて，その一般化を証明することで様々な帰結を導きだしている．この論文のイントロを読むと，その辺りの話題が離散数学，計算量理論，暗号理論でどのような役割を果たしていて，どういう歴史をたどってきたかということを少しは見ることができて，楽しい．面白い．