Santa Fe Institute

Happening now at SFI: Working group seeks new algorithms for an old problem

May 16, 2016 10:02 a.m.

Symmetry appears readily in nature: on the petals of a sunflower or the spires of a snowflake. But not all symmetries are alike. Flip a square horizontally, vertically, or diagonally – these are reflectional symmetries – and it looks the same. That flipping, though, differs from the rotational symmetry of a pinwheel spinning about its center.

Deciding whether two symmetries are alike is a longstanding problem in group theory, the mathematical study of symmetry. This challenge, called the Group Isomorphism Problem, dates back more than 100 years. And it’s not just a mathematical curiosity: The problem has implications in fields as diverse as geology, particle physics, and chemistry.

For simple cases like squares and pinwheels, differences are easily spotted. But for larger objects or in higher dimensions, researchers require computers and algorithms. Theoretical computer scientist Josh Grochow, an SFI Omidyar Fellow, has organized a mid-May working group comprised of two group theorists and two computer scientists, to better understand the structure of the Group Isomorphism Problem.

“It’s a pretty unique situation to have these two communities together, working on the same problem but with different goals, agendas, and techniques,” he says. “We think that each will benefit from its interaction with the other.”

Grochow’s collaborators include mathematician Peter Brooksbank from Bucknell University, mathematician James Wilson from Colorado State University, and computer scientist Youming Qiao from the University of Technology, Sydney, in Australia.

Grochow and Qiao have collaborated for years on the problem; so have Brooksbank and Wilson. Recent research from each group “made it clear that our ideas might be fruitfully combined,” says Grochow. He notes that Wilson first suggested combining forces, and the working group at SFI was a natural early step. Grochow says he sees this mid-May meeting as the first in a years-long effort. “Truly resolving the problem could take decades or longer,” he says. “We already see enough stepping stones that we think we could make progress for several years.” 

More about the working group here

All SFI NewsAbout SFIFollow SFISupport SFISFI Home

News Media Contact

  • John German
  • Director of Communications
  • (505) 946-2798


Parallax newsletter
Bulletin magazine
Follow SFI

SFI in the News