ECCC-Report TR09-078https://eccc.weizmann.ac.il/report/2009/078Comments and Revisions published for TR09-078en-usSat, 19 Sep 2009 12:58:14 +0300
Paper TR09-078
| A Probabilistic Inequality with Applications to Threshold Direct-product Theorems |
Falk Unger
https://eccc.weizmann.ac.il/report/2009/078We prove a simple concentration inequality, which is an extension of the Chernoff bound and Hoeffding's inequality for binary random variables. Instead of assuming independence of the variables we use a slightly weaker condition, namely bounds on the co-moments.
This inequality allows us to simplify and strengthen several known direct-product theorems and establish new threshold direct-product theorems. Threshold direct-product theorems are statements of the following form: If one instance of a problem can be solved with probability at most $p$, then solving significantly more than a $p$-fraction among multiple instances has negligible probability.
Using our concentration inequality we show how to obtain threshold (and standard) direct-product theorems from known XOR Lemmas. We give examples of this approach and establish (threshold) direct-product theorems for quantum XOR games, quantum random access codes, 2-party and multi-party communication complexity, and circuits. Similar results can be obtained for other models of computation, e.g. polynomials over $GF(2)$ and query complexity.
We believe that our inequality has applications in other contexts as well.Sat, 19 Sep 2009 12:58:14 +0300https://eccc.weizmann.ac.il/report/2009/078