Join 3,512 readers in helping fund MetaFilter (Hide)

2 posts tagged with computerscience by albrecht.
Displaying 1 through 2 of 2.

Related tags:
+ (11)
+ (10)
+ (10)
+ (9)
+ (6)
+ (5)
+ (5)
+ (5)
+ (5)
+ (5)
+ (4)
+ (4)
+ (4)


Users that often use this tag:
Blazecock Pileon (4)
chunking express (3)
albrecht (2)
parudox (2)
Foci for Analysis (2)
jedicus (2)
Wolfdog (2)

Classic Nintendo Games are (NP-)Hard

Some (slightly generalized) classic Nintendo games are NP-Hard. [pdf] [more inside]
posted by albrecht on Mar 13, 2012 - 59 comments

Breaking the Coppersmith-Winograd barrier

For twenty years, the fastest known algorithm to multiply two n-by-n matrices, due to Coppersmith and Winograd, took a leisurely O(n^2.376) steps. Last year, though, buried deep in his PhD thesis, Andy Stothers discussed an improvement to O(n^2.374) steps. And today, Virginia Vassilevska Williams of Berkeley and Stanford, released a breakthrough paper [pdf] that improves the matrix-multiplication time to a lightning-fast O(n^2.373) steps. [via] [more inside]
posted by albrecht on Nov 29, 2011 - 50 comments

Page: 1