Before revision:  This is optimal in the sense that as long as the exponent of T is independent of n, T, it cannot be improved while retaining the dependency on n , as follows from the lower bound of Eden and Rosenbaum [APPROX/RANDOM 2018].
After revision:  This is optimal in the sense that as long as the exponent of T is independent of n, T, it cannot be improved while retaining the dependency on n ; this as follows from the lower bound of Eden and Rosenbaum [APPROX/RANDOM 2018].