(Relatively) new algorithm for parallel solution of a linear system

I got this interesting link from Igor Carron, the master of compressed sensing. Here is a quote from his blog post:

 A Randomized Parallel Algorithm with Run Time $O(n^2)$ for Solving an $n \times n$ System of Linear Equations by Joerg Fliege. The abstract reads:

In this note, following suggestions by Tao, we extend the randomized algorithm for linear equations over prime fields by Raghavendra to a randomized algorithm for linear equations over the reals. We also show that the algorithm can be parallelized to solve a system of linear equations $A x = b$ with a regular $n \times n$ matrix $A$ in time $O(n^2)$, with probability one. Note that we do not assume that $A$ is symmetric.

==> Looks like a cool and simple algorithm to implement in parallel for solving linear system. If anyone implemented it in parallel let me know! Also if you have some matlab code that would be interesting.

When digging slightly dipper I saw the following claim in the paper:

So it seems like an O(n^3) operations after all. (The O(n^2) is achieved on each of the n cpus).