Theory of Computing
-------------------
Title     : Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications
Authors   : Avi Wigderson and David Xiao
Volume    : 4
Number    : 3
Pages     : 53-76
URL       : http://www.theoryofcomputing.org/articles/v004a003

Abstract
--------

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.