This one is even better than the last seminar announcement I forwarded to
this list! (And -this- time, REMEMBER: replying to this message will
-not- send mail that Shamir will get; it will only send everyone on
Cube-Lovers a piece of junk mail.)

 DATE: Friday, May 22, 1987
               TIME: Refreshments: 1:45PM
                     Lecture:      2:00PM
PLACE: NE43-512A

HOW TO SOLVE THE CUBE

Adi Shamir
Applied Math
The Weizmann Institute, Israel

Given k generators for a permutation group G, it is easy to verify that a
permutation belongs to G but NP-complete to find a short representation of
the permutation as a product of the generators. In this talk we describe a
new algorithm for computing the shortest representation which significantly
improves the time/space complexities of previous algorithms. The new
algorithm is particularly interesting in the context of Rubik's cube since it
makes it possible to solve previously intractable problems such as finding
the shortest sequence of moves which fixes a given state or the optimal
subroutine for permuting certain subcubes, in just 2^40 time and 2^20 space,
compared to 2^80 time in previous algorithms.

Host: Prof. Ron Rivest