Linear programming in O(n3/ln n/L) operations

We show that the complexity to solve linear programming problems, using standard linear algebra, can be reduced to O([n(3)/ln n]L) operations, where n is the number of variables in a standard-form problem with integer data of bit size L. Our technique combines partial updating with a preconditioned conjugate gradient method, in a scheme first suggested by Nesterov and Nemirovskii.