ACCS Visiting Speaker:

Prof Gene Cooperman
Computer and Information Science at Northeastern University, Boston

Place: Room 621 GP South (Building 78)
Time: Tuesday 26 June 2007, 3:30pm Afternoon Tea, 4:00pm Seminar

Host: Prof George Havas

========Title and Abstract=====
Using Parallel Disk-Based Computing:  a New Record for Computer-Generated Solutions to Rubik's Cube

The question of the maximum number of moves needed to solve any state of Rubik's cube became a challenge problem for computer science almost since the invention of Rubik's cube in the late 1970s. In joint work with Daniel Kunkle, we recently showed that 26 moves suffice, and we hope soon to demonstrate that 25 moves suffice. An upper bound of 29 was found by Reid in 1995.  This bound was reduced to 27 in 2006 by Radu. The best upper bound is suspected to be~20.

The basis for our approach is two-fold: (1) We developed a new group-theoretic algorithm for fast simulation of moves; and (2) We use 7 terabyes of distributed parallel disk for intermediate storage of a data structure related to hash tables, but more suitable for disk streaming access. The group-theoretic algorithm allows us to multipy a symmetrized coset (large classes of states closed under symmetries) by a generator at a rate of more than 10 million moves per second.

As time permits, I will also briefly describe a new checkpointing package that can checkpoint distributed, multi-threaded processes with open files, such as the program being used in the computation of Rubik's cube. This part is joint work with Jason Ansel and Michael Rieker.

======Biography======
Gene Cooperman received his B.S. degree from the University of Michigan in honors math and physics, and his Ph.D. degree in Applied Mathematics from Brown University. He is currently a Professor of Computer and Information Science at Northeastern University, Boston. His research interests include parallel and high performance computing, and algebraic computations. Dr Cooperman is an associate editor of ACM Transactions on Mathematical Software (TOMS) and on the advisory board of the European Union SCIEnce project (Symbolic Computation in Europe). Dr Cooperman currently serves on three program committees of technical conferences in computational and parallel algebra and network computing. He is also head of the Institute for Complex Scientific Software (www.research.neu.edu/centers_institutes/software/) at Northeastern University. Dr Cooperman has published over 70 refereed publications.  For a list of publications, see: http://www.ccs.neu.edu/home/gene/papers.html