3,374 reputation
1031
bio website stanford.edu/~rrwill
location California
age
visits member for 4 years, 4 months
seen Apr 7 at 1:33
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