We discovered an error in the proof of the main theorem of "A Randomness-Efficient Sampler for Matrix-valued Functions and Applications", which appears as ECCC TR05-107 and also appeared in FOCS. We describe it below. This error invalidates all of the results concerning the expander walk sampler for matrix-valued functions.

Nevertheless, we are able to use a different technique to prove the main applications of the sampler that appear in that paper. These include a deterministic algorithm for constructing logarithmic-degree Cayley graphs on any group (derandomizing Alon-Roichman's theorem), and for the quantum hypergraph cover problem, described in Ahlswede-Winter. We state the correct result - the manuscript with their proof, under the title "Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications", is available as an ECCC report TR06-105 and also will appear on our homepages.

In this paper we give a randomness-efficient sampler for matrix-valued functions. Specifically, we show that a random walk on an expander approximates the recent Chernoff-like bound for matrix-valued functions of Ahlswede and Winter, in a manner which depends optimally on the spectral gap. The proof uses perturbation theory, and is a generalization of Gillman's and Lezaud's analyses of the Ajtai-Komlos-Szemeredi sampler for real-valued functions.

Derandomizing our sampler gives a few applications, yielding deterministic polynomial time algorithms for problems in which derandomizing independent sampling gives only quasi-polynomial time deterministic algorithms. The first (which was our original motivation) is to a polynomial-time derandomization of the Alon-Roichman theorem (see also Russell and Landau, Schulman and Loh): given a group of size $n$, find $O(\log n)$ elements which generate it as an expander. This implies a second application - efficiently constructing a randomness-optimal homomorphism tester, significantly improving the previous result of Shpilka and Wigderson}. The third is to a ``non-commutative'' hypergraph covering problem - a natural extension of the set-cover problem which arises in quantum information theory (see Ahlswede and Winter, Hayden-Leung-Shor-Winter), in which we efficiently attain the integrality gap when the fractional semi-definite relaxation cost is constant.