Skip to content

A Fast Graph Isomorphism Algorithm

November 11, 2015

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?
Read more…

The World Series Of Complexity Theory

November 9, 2015

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…

A Big Result On Graph Isomorphism

November 4, 2015

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.
Read more…

Ghosts in Princeton

November 1, 2015

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.
Read more…

Guessing Conjectures

October 29, 2015

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.
Read more…

Rankings Versus Ratings

October 22, 2015

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.
Read more…

Is The Hot Hand Fallacy A Fallacy?

October 12, 2015

A simple idea that everyone missed, and more?

Composite of src1, src2, src3

—A myth of a myth of a myth?

Joshua Miller and Adam Sanjurjo (MS) have made a simple yet striking insight about the so-called hot hand fallacy.

Today Ken and I want to discuss their insight, suggest an alternate fix, and reflect on what it means for research more broadly.
Read more…


Get every new post delivered to your Inbox.

Join 2,642 other followers