bio | website | stanford.edu/~rrwill |
---|---|---|
location | California | |
age | ||
visits | member for | 4 years, 4 months |
seen | Apr 7 at 1:33 | |
stats | profile views | 1,615 |
Interested in algorithms, complexity, and anything that the rest of mathematics can say about these two.
Feb 18 |
awarded | Nice Answer |
Dec 16 |
awarded | Yearling |
Dec 10 |
awarded | Nice Answer |
Nov 22 |
awarded | Enlightened |
Nov 22 |
awarded | Nice Answer |
Nov 5 |
comment |
Finding a cycle of fixed length
Not sure what you're asking. There can be $\Omega(n^4)$ cycles of length 4 in a graph, so $O(n^4)$ time is the best you can hope for asymptotically if you want to list all 4-cycles. If you're asking how to get the above algorithm to produce a 4-cycle in $O(n^2)$ time when one exists, that's also pretty obvious... |
Oct 11 |
awarded | Caucus |
Oct 11 |
awarded | Constituent |
Sep 10 |
awarded | Nice Answer |
Jun 25 |
awarded | computational-complexity |
Jun 3 |
awarded | Good Answer |
Dec 16 |
awarded | Yearling |
Jun 26 |
awarded | Nice Answer |
Apr 16 |
awarded | Nice Answer |
Mar 15 |
awarded | Nice Answer |
Dec 17 |
awarded | Yearling |
Nov 21 |
awarded | Popular Question |
Nov 9 |
awarded | Popular Question |
Jun 7 |
awarded | Nice Answer |
Mar 12 |
comment |
Strassen Algorithm 7 multiplications
What Landsberg claims is stronger than what Hopcroft-Kerr and Winograd show. Landsberg claims that the border rank of $2 \times 2$ matrix multiplication is 7; this is stronger than proving that the rank of matrix multiplication is 7. Nevertheless, it looks like Landsberg patched his proof at arxiv.org/abs/math/0407224 |