Complexity of linear programming
See the paper &quot;A parallel approximation algorithm for positive linear programming.&quot; by Luby and Nisan. (Some kinds of) linear programs can be approximated in log^(O(1)) n time.