WSJ Meets Group Algorithms

Cropped from source

Jessica Fridrich is a Distinguished Professor of Electrical and Computer Engineering at Binghamton University. She is an expert on data hiding, that is, steganography. She has over 34,000 citations—impressive. A lot more than most of us. She also has worked on the famous Rubik’s cube.

Today we look at her work on Rubik’s cube, the WSJ’s interest in Rubik’s cube, and what both say—and don’t say—about fundamental algorithms.

By the way, WSJ stands for the Wall Street Journal—the American newspaper of business. The WSJ has shown great interest in the Rubik’s cube puzzle and has run many articles over the years on it.

Recall the cube puzzle was invented…of course you know all about Rubik’s cube. You probably have owned one at one time. Right. Just for a refresher:

The Rubik’s Cube is a 3-D combination puzzle invented in 1974 by Hungarian sculptor and professor of architecture Ernő Rubik. As of January 2009, 350 million cubes had been sold worldwide, making it the world’s top-selling puzzle game. It is widely considered to be the world’s best-selling toy.

But you may not know all about Fridrich.

Speed Solving

Fridrich was one of the progenitors of speed cubing. She took part in the First World Championship in 1982 in Budapest, next-door to her native Czechoslovakia. She finished in the middle of the pack with a time of 29.11 seconds from a randomly well-mixed starting cube position. Her thoughts on how the cubes could be better prepared for speed are recorded on her page about the tournament.

At the Second World Championship, she improved her average time to 20.48 seconds and placed 2nd. She had the two fastest solves in the finals but lost on average-of-median-three-of-five. That championship took place in Toronto—in 2003. She is at a loss to explain why there was such a gap. Usually an athlete—in this case a mathlete?—is on the downswing nearing age 40, but even as a self-described “old-timer,” she fended off all but one of a whole next generation.

Much of the credit goes to her solving method. She originated the “O” and “P” parts of the CFOP method. CFOP stands for: Cross, First 2 Layers, Orient Last Layer, Permute Last Layer. Versions of this are used my most top “cubers” to this day, and her name is often affixed to the method. In a 2008 profile of her, the New York Times quoted the 2003 winner as saying that Fridrich found the route up the mountain while the rest of the cubers optimize traversing ledges along it. And in 2012, the NYT quoted Olympic shot-putter Reese Hoffa as wanting “to learn the Fridrich Method of solving the puzzle, ‘which is what all of the best cubers use.'”

At this point, knowing our interest in chess, you might expect a Queen’s Gambit reference. But what we have here is not a story of Beth Harmon coming back from a life adjournment or Roy Hobbs in The Natural rejoining baseball almost 20 years after being shot. It’s about going overseas, earning a PhD, getting two research positions, writing early papers (under the name Jiri Fridrich), transitioning, then getting a faculty position leading to tenure while developing mathematical formulas and writing tons of code for systems to source photos and catch digital pirates and pornographers and other image fraudsters, then coming back to light up an or universe. Not to mention doing her own stunning photo art of the American Southwest.

Quicker Times and Cubes

Since 2003, the championships have been held every other year, thought the 2021 championships set for the Netherlands are uncertain owing to the pandemic. The youngsters soon broke through en-masse, and it strikes me that the cube technology improved so that the cubes are springier and lighter. The winning time fell almost 5 seconds to 15.10 in 2005 and hit 6.74 in 2019. That was not the world record, however—an incredible 3.47 seconds in 2018 by Yusheng Du, beating the previous record of Feliks Zemdegs by a whopping 3/4 of a second.

Fridrich, however, must claim a distinction no one may ever match. She learned how to solve the cube and traced out the performance of methods of doing so in 1981, months before she saw a cube, let alone owned one. Despite the “Bűvös Kocka” (“Magic Cube,” as Rubik called it) having been on shelves in neighboring Hungary for four years, with worldwide marketing by early 1980, they were hard to come by in her home city, Ostrava.

She found an article on solving the cube in a Russian magazine. It laid out the concept of group theory and the role of group commutators, which she learned to apply creatively in order to streamline actions. The first time she touched a cube was to help a friend put his back the way it was. A family visiting from France let her keep one, and later in 1981 she was finally able to purchase a few more. This invites analogy to working out chess without a board on a bedroom ceiling as depicted in The Queen’s Gambit.

We—Dick and Ken—must admit that neither of us has ever done this with the cubes we own, not fast, not slow. Yet we do understand the theory behind it. We believe we do.

Group Theory of the Cube

I (Dick) plan on explaining the theory by using a new toy that I have invented: The .

We will write the state as where each of is one of 1, 2, or 3. The operations allowed are the cyclic shift , which does

and the flip of the initial two elements:

Note there are 6 possible states. For the real Rubik’s cube, the number of states is just a little bit larger: 43,252,003,274,489,856,000. But the basic concept is the same. Suppose we are given the state

How fast can you get the initial state ? Apply :

This is a special case of the general result that any symmetric group is generated by two operations: a full cycle and a single flip. The key with the actual Rubik’s cube is since the group is larger and it has more operations that can be applied finding the group operations may be more difficult. But there are algorithms that can find them. See this for another article by Keith Conrad.

There are many more pages like that on the cube. But Fridrich still shows the seminal page she posted in “Winter 1996/97.” It links to other pages, ones that also credit other people, such as this explaining the algorithms in great pictorial detail. This was in the infancy of the Internet. Her pages are often credited with spurring the turn-of-the-millennium boom in Rubik’s cube which led to the revival of the championships in 2003. A 2016 New York Post article whose URL is titled, “how the Internet brought the Rubik’s cube back to life,” says:

The seeds for Rubik’s Cube’s rediscovery were sown on the internet. In the mid-1990s, a Rubik’s Cube champion-turned-computer-science professor at SUNY Binghamton posted her secrets of the Cube on a primitive Web 1.0 site on the university’s servers. Jessica Fridrich’s method spread and is today the most widely used technique to solve the puzzle.

See also this telling by the 2003 winner, Dan Knights. This shows how one person using spare time on the Internet can power up business.

Enter the WSJ

The WSJ has had an interest in Rubik’s cube for years. They had a long feature article last week titled, “How to Teach Professors Humility? Hand Them a Rubik’s Cube,” by Melissa Korn. It describes a faculty development challenge among several small colleges in which professors became students again. Last month they also had an article on symmetry by the mathematician Eugenia Cheng that mentioned the cube.

I recall several features the WSJ has run on the cube and its solvers. The 2011 article, “One Cube, Many Knockoffs, Quintillions of Possibilities,” led off with the Polish teenager Michal Pleskowicz winning the 2011 world championship with a time of 8.65 seconds, then discussed the performance of pirated cubes: “One reason Mr. Pleskowicz and a new generation of Rubik’s fanatics can solve the notoriously difficult puzzle in record time: They don’t use Rubik’s Cubes at all, instead substituting souped-up Chinese knockoffs engineered for speed…” Their 2014 article, “Rubik’s Cube Proves It’s Hip to Be Square,” profiled both Rubik and speed-solvers.

The feature I recall best was in 2018. It was titled, “A Thinking Person’s Guide to the Rubik’s Cube,” and subtitled, “What’s the best solution method—theory, algorithms or chance?” It was also by Eugenia Cheng. She begins by confessing, “I have always loved playing with a Rubik’s Cube, which combines logic with a satisfying tactile activity. I can solve it—getting each of the six sides to be one color—but not particularly quickly or cleverly.”

They also like its use for analogies. Scrolling through their advanced search—both Ken and I subscribe to the WSJ—we find:

• 2/12/21: “Running restaurants is now ‘a bit of a Rubik’s Cube,’ said Mr. Mosier, who reopened his casual cafes in late January.”
• 8/20/20, headline: “Reopening Schools Is So Complicated, New York Is Struggling to Schedule Classes Nation’s largest district is still hashing out basic details about the school day; ‘a multidimensional Rubik’s Cube’ of challenges.”
• 7/7/20: “The new [pandemic] rules have created a Rubik’s Cube of decisions for schools, which face unique challenges with each of their international student populations.”
• 5/26/20, about a home selling for $62 million: “Designed by Seattle-based architecture firm Olson Kundig, the house has interlocking boxes and planes resembling a Rubik’s cube…”
• 4/17/20, quoting Agriculture Secretary Sonny Perdue on the coronavirus relief program for farmers: “It will be a logistical Rubik’s Cube.”
• 11/14/19, about a retiree who started teaching business classes, keeping books for a non-profit business, and working on a ferry dock: “My society consists of able-bodied seamen, boat captains, truckers hauling bait and lobsters, fishermen, islanders and wide-eyed vacationers,” says Mr. Marshall. It’s “a constant Rubik’s cube. You never know what you’ll find.”

In all, using the WSJ advanced search, we find 239 hits for “Rubik” going back to 1980. We should mention in-passing that one of them is their 7/17/20 obituary for Ron Graham. We also find 7 hits for “Fridrich” over the same span. But they are all about the housing market, involving the Nashville-based realty Fridrich and Clarke.

Open Problems

I am happy to see that the WSJ has published multiple articles on a particular algorithmic task. I like that algorithms have been the center of articles. I wish they would talk more about important algorithms. Solving a Rubik’s cube is not an algorithm that is used every day: What about:

• Sorting
• Searching
• Dynamic Programming
• Fast Arithmetic

They do have Eugenia Cheng, who wrote a column comparing sorting algorithms. And they have written on algorithms used in trading and on social–media platforms and for policing and parole and bail decisions. But that tends away from fundamental algorithms where the math is the matter.

A 2018 WSJ article by Hannah Fry titled “Don’t Believe the Algorithm,” which begins with flaws in using facial recognition to find wanted suspects, brings us back toward Fridrich’s research. Might this all also raise discussion of “algorithms” for what and whom to cover?

[fixed name at end]