<?xml version="1.0" encoding="UTF-8"?><rss version="2.0"
	xmlns:content="http://purl.org/rss/1.0/modules/content/"
	xmlns:dc="http://purl.org/dc/elements/1.1/"
	xmlns:atom="http://www.w3.org/2005/Atom"
	xmlns:sy="http://purl.org/rss/1.0/modules/syndication/"
		>
<channel>
	<title>Comments on: 2.373</title>
	<atom:link href="http://www.scottaaronson.com/blog/?feed=rss2&#038;p=839" rel="self" type="application/rss+xml" />
	<link>http://www.scottaaronson.com/blog/?p=839</link>
	<description>The Blog of Scott Aaronson</description>
	<lastBuildDate>Thu, 23 May 2013 21:50:48 +0000</lastBuildDate>
	<sy:updatePeriod>hourly</sy:updatePeriod>
	<sy:updateFrequency>1</sy:updateFrequency>
	<generator>http://wordpress.org/?v=3.5.1</generator>
	<item>
		<title>By: Amir Shpilka on fast matrix multiplication &#124; MyCQstate</title>
		<link>http://www.scottaaronson.com/blog/?p=839#comment-53298</link>
		<dc:creator>Amir Shpilka on fast matrix multiplication &#124; MyCQstate</dc:creator>
		<pubDate>Tue, 25 Sep 2012 15:56:49 +0000</pubDate>
		<guid isPermaLink="false">http://www.scottaaronson.com/blog/?p=839#comment-53298</guid>
		<description><![CDATA[[...] : multiplying a column by a row matrix requires the computation of all  possible products. A lot of excitement was generated recently when the best previously known upper bound, due to Coppersmith and Vinograd [...]]]></description>
		<content:encoded><![CDATA[<p>[...] : multiplying a column by a row matrix requires the computation of all  possible products. A lot of excitement was generated recently when the best previously known upper bound, due to Coppersmith and Vinograd [...]</p>
]]></content:encoded>
	</item>
	<item>
		<title>By: Cup Sets, Sunflowers, and Matrix Multiplication &#124; Combinatorics and more</title>
		<link>http://www.scottaaronson.com/blog/?p=839#comment-35717</link>
		<dc:creator>Cup Sets, Sunflowers, and Matrix Multiplication &#124; Combinatorics and more</dc:creator>
		<pubDate>Fri, 09 Dec 2011 15:04:36 +0000</pubDate>
		<guid isPermaLink="false">http://www.scottaaronson.com/blog/?p=839#comment-35717</guid>
		<description><![CDATA[[...] =2.376, to 2.374 and 2.373 respectively. (See the discussions over Lipton&#8217;s blog (1,2), Shtetl optimized, and Computational [...]]]></description>
		<content:encoded><![CDATA[<p>[...] =2.376, to 2.374 and 2.373 respectively. (See the discussions over Lipton&#8217;s blog (1,2), Shtetl optimized, and Computational [...]</p>
]]></content:encoded>
	</item>
	<item>
		<title>By: techtings&#187; Key mathematical tool sees first advance in 24 years</title>
		<link>http://www.scottaaronson.com/blog/?p=839#comment-35710</link>
		<dc:creator>techtings&#187; Key mathematical tool sees first advance in 24 years</dc:creator>
		<pubDate>Fri, 09 Dec 2011 13:58:11 +0000</pubDate>
		<guid isPermaLink="false">http://www.scottaaronson.com/blog/?p=839#comment-35710</guid>
		<description><![CDATA[[...] knew a month ago that this was coming &#8211; I had a hell of a time keeping the secret,&#8221; wrote Scott Aaronson, another computer scientist and blogger, based at the Massachusetts Institute of [...]]]></description>
		<content:encoded><![CDATA[<p>[...] knew a month ago that this was coming &#8211; I had a hell of a time keeping the secret,&#8221; wrote Scott Aaronson, another computer scientist and blogger, based at the Massachusetts Institute of [...]</p>
]]></content:encoded>
	</item>
	<item>
		<title>By: Jr</title>
		<link>http://www.scottaaronson.com/blog/?p=839#comment-35239</link>
		<dc:creator>Jr</dc:creator>
		<pubDate>Mon, 05 Dec 2011 12:45:21 +0000</pubDate>
		<guid isPermaLink="false">http://www.scottaaronson.com/blog/?p=839#comment-35239</guid>
		<description><![CDATA[The Strassen/Coppersmith-Winograd/Strothers/Vassilevska line of results are purerly algebraic, right? Has the complexity of matrix multiplication been studied in other models, say on Turing machines?]]></description>
		<content:encoded><![CDATA[<p>The Strassen/Coppersmith-Winograd/Strothers/Vassilevska line of results are purerly algebraic, right? Has the complexity of matrix multiplication been studied in other models, say on Turing machines?</p>
]]></content:encoded>
	</item>
	<item>
		<title>By: Arul</title>
		<link>http://www.scottaaronson.com/blog/?p=839#comment-35193</link>
		<dc:creator>Arul</dc:creator>
		<pubDate>Sun, 04 Dec 2011 23:55:51 +0000</pubDate>
		<guid isPermaLink="false">http://www.scottaaronson.com/blog/?p=839#comment-35193</guid>
		<description><![CDATA[@Gabor: Comment #125 Thankyou]]></description>
		<content:encoded><![CDATA[<p>@Gabor: Comment #125 Thankyou</p>
]]></content:encoded>
	</item>
	<item>
		<title>By: Arul</title>
		<link>http://www.scottaaronson.com/blog/?p=839#comment-35192</link>
		<dc:creator>Arul</dc:creator>
		<pubDate>Sun, 04 Dec 2011 23:55:25 +0000</pubDate>
		<guid isPermaLink="false">http://www.scottaaronson.com/blog/?p=839#comment-35192</guid>
		<description><![CDATA[@Mark Blaser: Comment #66 &quot;whenever you raise the tensor
to a higher power, the improvement also shrinks geometrically&quot; Is there a proof for this?]]></description>
		<content:encoded><![CDATA[<p>@Mark Blaser: Comment #66 &#8220;whenever you raise the tensor<br />
to a higher power, the improvement also shrinks geometrically&#8221; Is there a proof for this?</p>
]]></content:encoded>
	</item>
	<item>
		<title>By: Markus Bläser</title>
		<link>http://www.scottaaronson.com/blog/?p=839#comment-35182</link>
		<dc:creator>Markus Bläser</dc:creator>
		<pubDate>Sun, 04 Dec 2011 22:38:48 +0000</pubDate>
		<guid isPermaLink="false">http://www.scottaaronson.com/blog/?p=839#comment-35182</guid>
		<description><![CDATA[@various people

1) Do not get me wrong. I like the work by Andrew and Virginia.
Both are great pieces of hard work.
But if you know the work by Coppersmith and Winograd (and from
what I read in other comments/posts, not many people do), then
you know the limitations of their methods before reading their papers. I do not have a formal lower bound of what you can get
out of the outer structure of the Coppersmith and Winograd 
tensor, but from what one typically observes, the improvement
shrinks geometrically with the power you take.

2) One possible reason why you do
not get anything from the third power is that it is the product
of the second and the first power. The second power is
superior to the first power. Note that taking the second,
fourth or whatever power is done for the sake of analysis.
In the construction, you take a huge power of the tensor.
And then it is better to think of it as a product of
second powers of the tensor than of a product of 
second powers as well as first powers. (Again, I cannot
prove this.)

3) Ian Gordon, the internal examiner, and myself told
Andrew after his viva to put a preprint online as soon 
as possible. Read the update in the post why he did not.

4) &quot;The calculations in Stother&#039;s paper are correct&quot; in my
comment means that they are not wrong. 
Some comments before raised the question whether there 
was a serious flaw in Stother&#039;s work. It is not.]]></description>
		<content:encoded><![CDATA[<p>@various people</p>
<p>1) Do not get me wrong. I like the work by Andrew and Virginia.<br />
Both are great pieces of hard work.<br />
But if you know the work by Coppersmith and Winograd (and from<br />
what I read in other comments/posts, not many people do), then<br />
you know the limitations of their methods before reading their papers. I do not have a formal lower bound of what you can get<br />
out of the outer structure of the Coppersmith and Winograd<br />
tensor, but from what one typically observes, the improvement<br />
shrinks geometrically with the power you take.</p>
<p>2) One possible reason why you do<br />
not get anything from the third power is that it is the product<br />
of the second and the first power. The second power is<br />
superior to the first power. Note that taking the second,<br />
fourth or whatever power is done for the sake of analysis.<br />
In the construction, you take a huge power of the tensor.<br />
And then it is better to think of it as a product of<br />
second powers of the tensor than of a product of<br />
second powers as well as first powers. (Again, I cannot<br />
prove this.)</p>
<p>3) Ian Gordon, the internal examiner, and myself told<br />
Andrew after his viva to put a preprint online as soon<br />
as possible. Read the update in the post why he did not.</p>
<p>4) &#8220;The calculations in Stother&#8217;s paper are correct&#8221; in my<br />
comment means that they are not wrong.<br />
Some comments before raised the question whether there<br />
was a serious flaw in Stother&#8217;s work. It is not.</p>
]]></content:encoded>
	</item>
	<item>
		<title>By: What is the worse case time complexity of matrices multiplication in Matlab? - Quora</title>
		<link>http://www.scottaaronson.com/blog/?p=839#comment-35170</link>
		<dc:creator>What is the worse case time complexity of matrices multiplication in Matlab? - Quora</dc:creator>
		<pubDate>Sun, 04 Dec 2011 18:45:28 +0000</pubDate>
		<guid isPermaLink="false">http://www.scottaaronson.com/blog/?p=839#comment-35170</guid>
		<description><![CDATA[[...] Peripheral point: It seems that new lower bounds have been discovered since Coppersmith-Winograd:http://www.scottaaronson.com/blo...Comment downvoted &#8226; 10:45amCannot add reply if you are logged out.10:45am&#160;Add [...]]]></description>
		<content:encoded><![CDATA[<p>[...] Peripheral point: It seems that new lower bounds have been discovered since Coppersmith-Winograd:<a href="http://www.scottaaronson.com/blo" rel="nofollow">http://www.scottaaronson.com/blo</a>&#8230;Comment downvoted &bull; 10:45amCannot add reply if you are logged out.10:45am&nbsp;Add [...]</p>
]]></content:encoded>
	</item>
	<item>
		<title>By: The Meaning of Omega &#171; Gödel&#8217;s Lost Letter and P=NP</title>
		<link>http://www.scottaaronson.com/blog/?p=839#comment-35137</link>
		<dc:creator>The Meaning of Omega &#171; Gödel&#8217;s Lost Letter and P=NP</dc:creator>
		<pubDate>Sun, 04 Dec 2011 13:03:01 +0000</pubDate>
		<guid isPermaLink="false">http://www.scottaaronson.com/blog/?p=839#comment-35137</guid>
		<description><![CDATA[[...] note that Markus Bl&#228;ser has contended in a comment that the extension of CW used by both new papers has limitations, and we infer that some other [...]]]></description>
		<content:encoded><![CDATA[<p>[...] note that Markus Bl&auml;ser has contended in a comment that the extension of CW used by both new papers has limitations, and we infer that some other [...]</p>
]]></content:encoded>
	</item>
	<item>
		<title>By: DI</title>
		<link>http://www.scottaaronson.com/blog/?p=839#comment-35134</link>
		<dc:creator>DI</dc:creator>
		<pubDate>Sun, 04 Dec 2011 12:02:20 +0000</pubDate>
		<guid isPermaLink="false">http://www.scottaaronson.com/blog/?p=839#comment-35134</guid>
		<description><![CDATA[I tend to agree with Farbod.
Time 1: Williams lowers w
Time 2: Williams discovers the work of Stothers. As this is very related to her work, she should read this and verify whether the result of Stothers is correct. It seems that this is what William did because after all, she can apply some Sthothers&#039; techniques to simplify some proofs.
Time 3 (at the moment of communicating the result) : Williams did already read in details  the Stothers&#039; work and cannot find any flaw in it (otherwise she should mention it), she should realize herself that Stothers&#039; work is the first that breaks CW barrier. She did choose however a title that make her result as the first that breaks CW barrier.

I also agree with Cohn: if there is no serious flaw in Stothers&#039; work, we should credit Stothers&#039; work as the first that breaks CW barrier. The Williams&#039;s work could be considered as an independent great result and vast improvement on Stothers&#039; work.]]></description>
		<content:encoded><![CDATA[<p>I tend to agree with Farbod.<br />
Time 1: Williams lowers w<br />
Time 2: Williams discovers the work of Stothers. As this is very related to her work, she should read this and verify whether the result of Stothers is correct. It seems that this is what William did because after all, she can apply some Sthothers&#8217; techniques to simplify some proofs.<br />
Time 3 (at the moment of communicating the result) : Williams did already read in details  the Stothers&#8217; work and cannot find any flaw in it (otherwise she should mention it), she should realize herself that Stothers&#8217; work is the first that breaks CW barrier. She did choose however a title that make her result as the first that breaks CW barrier.</p>
<p>I also agree with Cohn: if there is no serious flaw in Stothers&#8217; work, we should credit Stothers&#8217; work as the first that breaks CW barrier. The Williams&#8217;s work could be considered as an independent great result and vast improvement on Stothers&#8217; work.</p>
]]></content:encoded>
	</item>
</channel>
</rss>
