News for hackers. Stuff that matters.
Re:Short algorithm, long-range consequences by robrenaud on Friday March 01, 2013 @04:42PM (#5307119)
> an algorithm that solved graph Laplacians in “nearly linear time,” meaning that the algorithm’s running time didn’t increase exponentially with the size of the problem.

MIT, I expected more from you.

Re:Short algorithm, long-range consequences by LukeShu on Friday March 01, 2013 @11:56PM (#5308505)
The phrase "nearly linear time" come from the paper.

However, the paper gives a better definition:

When we refer to a nearly linear time SDD system solver we mean an an algorithm that computes such a x in time O(mlog^c(n)logε⁻¹) where m is the number of nonzero entries in A and c ≥ 0 ∈ ℝ is a fixed constant.

Re:Short algorithm, long-range consequences by _delirium on Saturday March 02, 2013 @12:13AM (#5308540)
The term "nearly linear time" is fine. The next part of that sentence is where the problem arises: it suggests that the opposite of "nearly linear", and the status quo, is that running time "increase[s] exponentially". But the existing standard algorithms already scale polynomially, not exponentially.
Re:Short algorithm, long-range consequences by mitchi on Friday March 01, 2013 @04:52PM (#5307165)
This article is probably not written by the CS department!
Re:Short algorithm, long-range consequences by jberryman on Saturday March 02, 2013 @12:46AM (#5308623)
Does everything have to turn into a dick-waving contest around here? Just send a correction if you care.
Re:Short algorithm, long-range consequences by verroq on Saturday March 02, 2013 @02:54AM (#5308904)
Looks like somebody else doesn't know what near-linear means.
Re:Short algorithm, long-range consequences by pavpanchekha on Saturday March 02, 2013 @11:04AM (#5309851)
In colloquial terminology, x^2 is an exponential. This isn't actually an important part of the article. I don't feel that a paragraph explaining why "Polynomial time" is bad (but not too bad) would improve the article.