Before revision:  The\pm  number of arithmetic operations needed to compute the next vertex in the path is polynomial in n, m and log k.
After revision:  The\pm 1 constraint matrices, our second contribution is an iterative algorithm which exploits the largest absolute value \alpha of the entries in the constraint matrix. We show that the length of the simplex path generated by the iterative algorithm is in O(n^2k \log(nk\alpha)). In particular, if \alpha is bounded by a polynomial in n, k, then the length of the simplex path is in O(n^2k \log(nk)). For both algorithms, the number of arithmetic operations needed to compute the next vertex in the path is polynomial in n, m and log k.