Posted on the arXiv: Twenty-Five Moves Suffice for the Rubik's Cube. Tomas Rokicki (Stanford trained computer scientist [I didn't know CS can be listed on the Math Genealogy Project...]; logic puzzle enthusiast; and author of dvips) showed using exhaustive computer computation (with a bit of theoretical mangling to reduce the configuration space) that there exists no configurations of the Rubik's cube that requires 26 moves or more, putting in a new upper bound for optimal solution at 25. (The previous record was 26.)

This is exciting, but still not satisfactory. While we know that there exist several configurations that require at least 20 moves to solve, there has not yet been any example constructed that requires at least 21 moves to solve. So the practical lower bound for optimal solution is 20. The gap between the lower bound and the upper bound is rather ugly. Ideally one would like a theoretical proof for a sharp upper bound of the number of moves required to solve a Rubik's cube.

While I am at it, here's a page with many cute Rubik's cube patterns and the minimal length moves required to achieve them.