Before revision:  Second, we reduce 1/\gamma from exponential in d to roughly d^{3/2}/\varepsilon^2 (where d is the maximum size of the matrices  ), and to nearly linear (roughly d/\varepsilon^2) for matrices M_i of sizes within a constant factor of each other.
After revision:  Second, we reduce 1/\gamma from exponential in d to roughly d^{3/2}/\varepsilon^2 (where d is the maximum size of the matrices M_i ), and to nearly linear (roughly d/\varepsilon^2) for matrices M_i of sizes within a constant factor of each other.