While we wait for Laci ${\dots}$

László Babai just gave his first talk on his new graph isomorphism (GI) algorithm. The photo was taken at the talk and posted by several people.

Today we want to discuss his talk, but ${\dots}$

But we were not there. Nor were we able to send a GLL representative there to hear the talk. There are twitter feeds here and here. The former, by Gabriel Gaster, gives a running textual description, but otherwise we are still pretty in the dark as to the details of the algorithm.

Or are we?

László’s three talks

 Chicago Chronicle source

László Babai must be busy getting ready for his series of talks.

Today Ken and I wish to discuss one issue that has come up in comments about his result.

By the way, the big event this Tuesday is not the Republican Debate on Fox, but Laci’s talk. It’s too bad for Chicago that the Cubs didn’t reach this year’s World Series, but these talks will make up for it. Read more…

Jumping GI down from the nearly-exponential neighborhood to the nearly-polynomial one

László Babai is one of the world experts on complexity theory, especially related to groups and graphs. He also recently won the 2015 ACM Knuth Prize, for which we congratulate him.

Today we wish to discuss a new result that he has announced that will place graph isomorphism almost in polynomial time.

Kurt Gödel in popular culture and answers to Thursday’s problems

 Levi Weaver source

Kurt Gödel may yet make it to Broadway. He already splashed across the silver screen in the 1994 Meg Ryan-Tim Robbins comedy I.Q. as the roly-poly sidekick of Walter Matthau playing Albert Einstein. He was pressed into retro vinyl by Levi Weaver for his 2011 album The Letters of Dr. Kurt Gödel. He features in the major Japanese manga series Negima! These borrowings may be incomplete or inconsistent, but with Gödel that’s par, no?

Today we consider Gödel’s impact on popular culture and give answers to the conjectures in Thursday’s post.

How well can we guess the right side of yes/no questions?

Takaaki Kajita and Arthur McDonald won the 2015 Nobel Prize in Physics for their discovery that neutrinos have mass. Although some physicists had shown as early as the 1950s that standard particle models could accommodate neutrinos with mass, there was no compelling reason for it. Moreover, the most-discussed terms for neutrino mass lack the desirable mathematical property of renormalizability. So most physicists of the last century guessed that neutrinos would be massless like photons are.

Today Ken and I wish to talk about guessing the answers to problems and conjectures in mathematics.

Handling both with the amazing generalized Kendall tau distance

Michelle Kwan was one of the last great figure skaters to compete under the historic “6.0” ranking system. She won the world championship five times under that system but was a squeaker second in the 1998 Winter Olympics and a more-distant third in 2002. An injury on the eve of the 2006 Winter Olympics prevented her from competing under the new and current system, which involves a complex numerical rating formula.

Today we discuss rankings versus ratings with an eye to complexity and managing them by common tools.