Solving Rubik’s Cube requires 25 or fewer moves

March 29th, 2008

Tomas Rokicki has written up a proof that any Rubik’s Cube configuration can be solved in 25 or fewer moves. In his paper, Twenty-Five Moves Suffice for Rubik’s Cube, Rokicki proves that there are no configurations that can be solved in exactly 26 moves. Taken with earlier results, this means that 25 movies should suffice for any solution.

“How many moves does it take to solve Rubik’s Cube? Positions are known that require 20 moves, and it has already been shown that there are no positions that require 27 or more moves; this is a surprisingly large gap. This paper describes a program that is able to find solutions of length 20 or less at a rate of more than 16 million positions a second. We use this program, along with some new ideas and incremental improvements in other techniques, to show that there is no position that requires 26 moves.”

KFC writes on the the physics arXiv blog that

“Rokicki’s proof is a neat piece of computer science. He’s used the symmetry of the cube to study transformations of the cube in sets, rather than as individual moves. This allows him to separate the “cube space” into 2 billion sets each containing 20 billion elements. He then shows that a large number of these sets are essentially equivalent to other sets and so can be ignored. Even then, to crunch through the remaining sets, he needed a workstation with 8GB of memory and around 1500 hours of time on a Q6600 CPU running at 1.6GHz.”

Rokicki is working to establish a bound of 24 moves and thinks that a bound of 20 can eventually be proved.

DHS National Cyber Security Center head has focus on leaderless organizations

March 29th, 2008

The appointment of Rod Beckstrom as the new head of the DHS National Cyber Security Center is interesting, if somewhat controversial. See, for example, the article Cybersecurity’s New Guard in BusnessWeek.

“The Bush Administration named Rod Beckström — entrepreneur, author, and decentralization expert — head of the National Cyber Security Center on Mar. 20. … Beckström, 47, is a Silicon Valley entrepreneur, a former derivatives trader, and a champion of conflict resolution in Africa. He’s better known as the founder of business collaboration software provider and as an author specializing in the agility of decentralized organizations than for connections inside the Beltway or expertise in cybersecurity.”

What’s somewhat controversial is his lack of a strong background in security or computer and communication technology — he’s an MBA. What’s interesting is his perspectives on and enthusiasm for decentralized and “leaderless” organizations, as articulated in his 2006 book The Starfish and the Spider: The Unstoppable Power of Leaderless Organizations, which I’ve not read, btw.

“Brafman and Beckstrom, a pair of Stanford M.B.A.s who have applied their business know-how to promoting peace and economic development through decentralized networking, offer a breezy and entertaining look at how decentralization is changing many organizations. The title metaphor conveys the core concept: though a starfish and a spider have similar shapes, their internal structure is dramatically different—a decapitated spider inevitably dies, while a starfish can regenerate itself from a single amputated leg. In the same way, decentralized organizations, like the Internet, the Apache Indian tribe and Alcoholics Anonymous, are made up of many smaller units capable of operating, growing and multiplying independently of each other, making it very difficult for a rival force to control or defeat them.”

In this age of decentralized information and communication systems and asymmetric warfare, I think Beckstrom might have a positive impact in his new position.

Visualizing social networks

March 29th, 2008

FAS Research social network visualizationsFAS Research is an Austrian company that specializes in social network analysis. Their site has a nice collections of social network visualizations that are artistic as well as informative.

How important is gravity?

March 17th, 2008

You drop a pen on the moon. Does the pen
a) float off into space,
b) float where it is, or
c) fall down?

Disturbingly, a majority answers either a or b. When asked, as a follow up, why astronauts don’t float when they’re on the moon, the majority answer is “because they have heavy boots.”

If you have a hard time believing this, I encourage you to start asking around. I asked some educated teenagers I know, and the first three of them answered either a or b.
“And why don’t astronauts float on the moon?”
“Special equipment.”
“Heavy boots.”
“Heavy boots.”

I mention this because a theme of SciBarCamp was “10 Things Everyone Should Know About Science”. This was motivated by organizer Eva Amsen’s recently surveying a number of people about to receive PhDs, and finding that none of them knew what a gene is. She felt strongly that everyone should know that genes are segments of DNA that code for proteins, and started to wonder what else everyone should know. We all made suggestions on a large poster board at the Friday reception, and then had a panel and heated discussion on the subject Sunday morning. Eva has promised to post the results on her blog.

Strangely (and somewhat embarrassingly) there was not a single scientific fact on the list. Everything was about the process of science, the purpose of science, the practice of science, etc. In everyone’s defense, these are important topics that are fun to argue about. Passionate on the subject, I used my turn to speak about infant behavior as a model of inquiry. But, given the chance at a do-over, would anyone disagree that gravity deserves a spot in the top 10? In fact, shouldn’t it be number 1?

Technorati tags:

Synthetic biology at SciBarCamp

March 17th, 2008

Tim’s away.
The blog is ours!
Now I can finally post about SciBarCamp, held last weekend in Toronto, and the most interesting meeting I’ve attended this millenium. Amongst its many highlights were two talks by Andrew Hessel. The first was about synthetic biology. Andrew helps run iGEM, which every year hands out “BioBricks” to high school and undergrad students around the world, and sees who can build the best genetic machines. Stunning successes have included a group of kids from Edinburgh who created a bacterium that changes the acidity of water, but only if there’s arsenic present. This enables individual wells to be tested at a cost of dimes instead of tens of dollars. (For a sickening account of why this is significant, click here, or here.) Another group invented a glowing bacterium which, I think, has a variety of computational and artistic applications.

The synthetic biology talk was part of a debate with Jim Thomas from etc, a group that monitors technology from a social justice perspective. Jim began by engendering sympathy for the Luddites, reminding us that in 1812, 14 Luddites were hanged near his alma mater in York, England. Before smashing things, Luddites would sometimes ask the people “is this harmful for the common good?”, and that’s the question Jim asked of synthetic biology. He didn’t exactly say yes, but he raised a number of concerns – security, safety, economic disruption, and concentration of corporate power. The only one which I really bought into was security; kids, as we know, do not use their creativity and hacking skills exclusively for good, and neither do adults. Part of Jim’s evidence was the case of Eckard Wimmer from Stony Brook, who built the polio virus from mail-order parts, just to show it could be done. The session ended before Andrew could respond.

Technorati tags:

Call for ISWC 2008 Research Papers

March 6th, 2008

The call for ISWC 2008 research papers for the Seventh International Semantic Web Conference is online. The track is co-chaired by Amit Sheth and Steffen Staab and has nineteen distinguished vice chairs and an program committee of experienced experts. Key dates for the research track are:

  • Abstracts due by 9 May 2008
  • Submissions due before 16 May 2008
  • Rebuttal phase during 14-16 June 2008
  • Notification sent by 11 July 2008
  • Camera ready due before 15 August 2008

Words your mobile phone is not allowed to say

March 3rd, 2008

Language models are widely used in processing both written and spoken language. They are used for part of speech tagging, sense tagging, disambiguation, text similarity metrics, and many other tasks, including predicting the words a person intends when typing on a telephone keypad. The last application has some interesting wrinkles, as this video we spotted on Language Log explains.

The most popular predictive text system in use today is T9, developed by Nuance Communications. You can check out the video’s examples using this T9 demo.

MIT NYTE project visualizes New York communications

March 1st, 2008

AP has an article, MIT Creates Picture of NY Communications, that highlights work of New York Talk Exchange (NYTE) project being done in the MIT SENSEable City Laboratory.

“For the past two months, 24 hours a day, MIT researchers have been collecting the electronic communications of millions of New Yorkers — but not for salacious gossip or to protect national security. They’ve been building a census that shows, neighborhood by neighborhood, New York’s telephone and Internet links to other cities across the planet and how those connections change over time.” (link)

Globe Encounters visualizes in real time the volumes of Internet data flowing between New York and cities around the world. The size of the glow on a particular city location corresponds to the amount of IP traffic flowing between that place and New York City. A greater glow implies a greater IP flow.

Visualizations from the NYTE project are part of the Design and the Elastic Mind exhibit at the Museum of Modern Art, which focuses on the use of technology in design.

“New York Talk Exchange illustrates the global exchange of information in real time by visualizing volumes of long distance telephone and IP (Internet Protocol) data flowing between New York and cities around the world. In an information age, telecommunications such as the Internet and the telephone bind people across space by eviscerating the constraints of distance. To reveal the relationships that New Yorkers have with the rest of the world, New York Talk Exchange asks: How does the city of New York connect to other cities? With which cities does New York have the strongest ties and how do these relationships shift with time? How does the rest of the world reach into the neighborhoods of New York?” (link)

The data was provided to the MIT researchers by AT&T from voice and Internet traffic after being anonymized to remove any personal information.