April 15, 2011 from 16:00 to 18:00 (Montreal/Miami time) On location
Colloquium presented by Morley Davidson
In July 2010 a team of four researchers led by Tomas Rokicki of Palo Alto announced that "God's Number" for the Rubik's Cube is 20, that is, any scramble can be solved in at most 20 moves (where a 90-degree or 180-degree twist counts as one move). Stated in group theory language, the problem asked for the diameter of the Cayley graph of the Rubik's Cube group using the so-called half-turn metric. The speaker had the privilege of being part of its solution, ultimately achieved through Rokicki's adaptation of Herbert Kociemba's two-step solution algorithm together with the solution of an auxiliary set cover problem and the help of Google's computing infrastructure. In this talk we will outline the thirty-year history of the problem and discuss the primary mathematical and computational breakthroughs that led to its solution.
Address
CRM, UdeM, Pav. André-Aisenstadt, 2920, ch. de la Tour, room 1360