https://rjlipton.wordpress.com/2012/08/09/a-new-way-to-solve-linear-equation... August 9, 2012 tags: <https://rjlipton.wordpress.com/tag/algorithms/>Algorithms, <https://rjlipton.wordpress.com/tag/amplification/>amplification, <https://rjlipton.wordpress.com/tag/finite-fields/>finite fields, <https://rjlipton.wordpress.com/tag/linear-system/>linear system, <https://rjlipton.wordpress.com/tag/randomness/>randomness by <https://rjlipton.wordpress.com/author/rjlipton/>rjlipton Impossible but true: a new approach to linear systems Prasad Raghavendra is an expert in many aspects of complexity theory, especially the foundations of approximation theory. He recently was a colleague at Georgia Tech, but now has moved on to Berkeley. He will be greatly missed at Tech. Today I want to talk about a brilliant new result that Prasad has on linear equations. I was recently at the advisory meeting for the Berkeley Simons Theory Institute. During the meeting we had two presentations on new areas, besides talks on planned special projects. One was given by Prasad on theory, but almost in passing he mentioned that he had a way to solve linear systems. I liked the whole talk, but his almost causal comment surprised me. It seemed to me to be an entire new approach to solving linear systems. My initial thought was it must be something well known, but I did not know it. As soon as he finished his talk we had a break, and I ran up to thank him for a wonderful talk. I quickly asked was his result on linear systems new? Or was it something I had missed? He answered to several of us, who now were waiting to hear his answer, that it was something that he had just proved. I was relieved: I am not completely out of it. I asked if we could write about this result and he agreed. Even better, he wrote up a <http://www.eecs.berkeley.edu/%7Eprasad/linsystems.pdf>draft paper with just the algorithm and its analysis, which are part of larger results and projects that were the body of his talk. Solving Linear Systems The solving of linear systems of equations is ancient, dating back to 600 BCE. It is of extreme importance, and still an active area of research. For arbitrary systems Gaussian Elimination is still quite powerful. A historical note, apparently Carl Gauss only used the method named after him on six-variable problems. In those days there was no notion of, I can solve the general case in time cubic in {n} . There was no "n": of course there was the letter "n," but not the notion of solving a problem of size determined by {n} . Of course now we have faster methods than this for general systems, methods that descend from the famous breakthrough of Volker Strassen. For special systems there are almost-linear-time methods, but these all require that the system have special structure, and work over the reals. ... --- co-chair http://ocjug.org/