DERANDOMIZED GRAPH PRODUCTS

Berman and Schnitger gave a randomized reduction from approximating MA X-SNP problems within constant factors arbitrarily close to 1 to appro ximating clique within a factor of n(epsilon) (for some epsilon). This reduction was further studied by Blum, who gave it the name randomize d graph products. We show that this reduction can be made deterministi c (derandomized), using random walks on expander graphs. The main tech nical contribution of this paper is in proving a lower bound for the p robability that all steps of a random walk stay within a specified set of vertices of a graph. (Previous work was mainly concerned with uppe r bounds for this probability.) This lower bound extends also to the c ase where different sets of vertices are specified for different time steps of the walk.