Posts
Carnegie Mellon University computer scientists and mathematicians
have resolved the last, stubborn piece of Keller's conjecture, a
geometry problem that scientists have puzzled over for 90 years by Byron Spice, Director of Media Relations, SCS - Marketing & Communications.
 |
| John Mackey, left, and Marijn Heule have pursued a math puzzle known as Keller's conjecture for decades. They found a solution by translating it into satisfiability problem. Photo: for Heule: Stephen Henderson. |
"I was really happy when we solved it, but then I was a little sad that the problem was gone," said John Mackey, a teaching professor in the Computer Science Department (CSD) and Department of Mathematical Sciences who had pursued Keller's conjecture since he was a graduate student 30 years ago. "But then I felt happy again. There's just this feeling of satisfaction."
The solution was yet another success for an approach pioneered by Marijn Heule, an associate professor of computer science who joined CSD last August...
Even with a high-quality translation, the number of combinations to be checked in dimension seven was mind-boggling — a number with 324 digits — with a solution nowhere in sight even with a supercomputer. But Heule and the others applied a number of tricks to reduce the size of the problem. For instance, if one data configuration proved unworkable, they could automatically reject other combinations that relied on it. And since much of the data was symmetrical, the program could rule out mirror images of a configuration if it reached a dead end in one arrangement.
Using these techniques, they reduced their search to about a billion configurations. They were joined in this effort by David Narvaez, a Ph.D. student at the Rochester Institute of Technology, who was a visiting researcher in the fall of 2019.
Source: Carnegie Mellon University News
