He might be referring to this: http://arxiv.org/pdf/0811.3171v3.pdf http://arxiv.org/pdf/0811.3171v3.pdf So, if the question you want to ask is "what is some p

He might be referring to this: http://arxiv.org/pdf/0811.3171v3.pdf http://arxiv.org/pdf/0811.3171v3.pdf So, if the question you want to ask is "what is some property of the solution of the (sparse) set of linear equations" rather than wanting to know the (inherently O(n)) solution itself, you can get exponential speedup.