Volume 4 (2008) Article 3 pp. 53-76

Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications

by Avi Wigderson and David Xiao

Received: November 28, 2007
Published: May 15, 2008
DOI: 10.4086/toc.2008.v004a003

Download article from ToC site:
[PS (439K)]    [PS.GZ (121K)]    [PS.ZIP (121K)]
[PDF (261K)]    [DVI (221K)]    [TeX (63K)]
Misc.:
[HTML Bibliography] [Bibliography Source] [BibTeX] 
[About the Author(s)]
Keywords: Chernoff bound, matrix-valued, derandomization, pessimistic estimators
Categories: concentration inequalities, derandomization, property testing, expanders, Cayley graphs, quantum, random sampling
ACM Classification: G.3, G.2.2, F.2.1, F.1.2
AMS Classification: 68W20, 68R10, 60F10, 20D60, 81P68, 15A18

Abstract: [Plain Text Version]

Ahlswede and Winter [IEEE Trans. Inf. Th. 2002] 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 [JCSS 1988]). As a consequence, we derandomize an efficient construction by Alon and Roichman [RSA 1994] of an expanding Cayley graph of logarithmic degree on any (possibly non-abelian) group. This gives an optimal solution to the homomorphism testing problem of Shpilka and Wigderson [STOC 2004]. We also apply these pessimistic estimators to the problem of solving semidefinite covering problems, thus giving a deterministic algorithm for the quantum hypergraph cover problem of Ahslwede and Winter.

The results above appear as theorems in our paper "A randomness-efficient sampler for matrix-valued functions and applications" [FOCS 2005, ECCC 2005], as consequences of the main claim 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 claim 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 despite our inability to prove the expander walk sampler theorem for matrix-valued functions.