Title :
A Probabilistic Inequality with Applications to Threshold Direct-Product Theorems
Author_Institution :
EECS Dept., UC Berkeley, Berkeley, CA, USA
Abstract :
We 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. Results of this kind are crucial when distinguishing whether a process succeeds with probability s or c, for 0 < s < c < 1. Here standard direct-product theorems are of no help since even a process which can solve one instance with probability c will only be able to solve all k instances with exponentially small 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 obtain (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). It is well-known that direct-product theorems and XOR Lemmas are "essentially" equivalent. We show that one direction is often even tight: going from XOR Lemmas to (threshold) direct-product theorems is possible in an information-theoretically optimal way. We believe that our inequality has applications in other contexts as well.
Keywords :
probability; Chernoff bound; Hoeffding inequality; XOR Lemmas; binary random variables; direct product theorems; multiparty communication circuits; multiparty communication complexity; probabilistic inequality; simple concentration inequality; threshold direct product theorems; Application software; Circuits; Complexity theory; Computational modeling; Computer science; Game theory; Polynomials; Quantum mechanics; Random variables; USA Councils; Chernoff bound; Concentration inequality; Direct-product Theorem; XOR Lemma;
Conference_Titel :
Foundations of Computer Science, 2009. FOCS '09. 50th Annual IEEE Symposium on
Conference_Location :
Atlanta, GA
Print_ISBN :
978-1-4244-5116-6
DOI :
10.1109/FOCS.2009.62