Loading...
Please wait, while we are loading the content...
Similar Documents
Derandomizing the aw matrix-valued chernoff bound using pessimistic estimators and applications (2006).
| Content Provider | CiteSeerX |
|---|---|
| Author | Wigderson, Avi Xiao, David |
| Abstract | Ahlswede and Winter [AW02] introduced a Chernoff bound for matrix-valued random variables, which is a non-trivial generalization of the usual Chernoff bound for real-valued random variables. We present an efficient derandomization of their bound using the method of pessimistic estimators (see Raghavan [Rag88]). As a consequence, we derandomize a construction of Alon and Roichman [AR94] (see also [LR04, LS04]) to efficiently construct an expanding Cayley graph of logarithmic degree on any (possibly non-abelian) group. This also gives an optimal solution to the homomorphism testing problem of Shpilka and Wigderson [SW04]. We also apply these pessimistic estimators to the problem of solving semi-definite covering problems, thus giving a deterministic algorithm for the quantum hypergraph cover problem of [AW02]. The results above appear as theorems in the paper [WX05a] (see also [WX05b]), as consequences to the main theorem of that paper: a randomness efficient sampler for matrix valued functions via expander walks. However, we discovered an error in the proof of that main theorem (which we briefly describe in the appendix). That main theorem stating that the expander walk sampler is good for matrix-valued functions thus remains open. One purpose of the current paper is to show that the applications in that paper hold true despite our inability to prove the expander walk sampler theorem for matrix-valued functions. 1 |
| File Format | |
| Publisher Date | 2006-01-01 |
| Access Restriction | Open |
| Subject Keyword | Pessimistic Estimator Main Theorem Aw Matrix-valued Chernoff Matrix-valued Function Randomness Efficient Sampler Deterministic Algorithm Optimal Solution Winter Aw02 Raghavan Rag88 Roichman Ar94 Non-trivial Generalization Wigderson Sw04 Expander Walk Sampler Semi-definite Covering Problem Real-valued Random Variable Paper Wx05a Logarithmic Degree Matrix-valued Random Variable Efficient Derandomization Usual Chernoff Bound Expander Walk Quantum Hypergraph Cover Problem Current Paper Cayley Graph Expander Walk Sampler Theorem Chernoff Bound |
| Content Type | Text |
