Skip to content

Snow And Theory

January 6, 2017

The 25th Anniversary of the ACO Program

Cropped from src1 & src2 in gardens for karma

Prasad Tetali and Robin Thomas are mathematicians at Georgia Tech who are organizing the Conference Celebrating the 25th Anniversary of the ACO Program. ACO stands for our multidisciplinary program in Algorithms, Combinatorics and Optimization. The conference is planned to be held starting this Monday, January 9–11, 2017.

Today I say “planned” because there is some chance that Mother Nature could mess up our plans.

Atlanta is expected to get a “major” snow storm this weekend. Tech was already closed this Friday. It could be that we will still be closed Monday. The storm is expected to drop 1-6 inches of snow and ice. That is not so much for cities like Buffalo in the north, but for us in Atlanta that is really a major issue. Ken once flew here to attend an AMS-sponsored workshop and play chess but the tournament was canceled by the snowfall described here. So we hope that the planned celebration really happens on time.

Attendance is free, so check here for how to register.

A Few Of The Talks

The program has a wide array of speakers. There are 25 talks in all including two by László Babai. I apologize for not listing every one. I’ve chosen to highlight the following for a variety of “random” reasons.

László Babai
Graph Isomorphism: The Emergence of the Johnson Graphs

Abstract: One of the fundamental computational problems in the complexity class NP on Karp’s 1973 list, the Graph Isomorphism problem asks to decide whether or not two given graphs are isomorphic. While program packages exist that solve this problem remarkably efficiently in practice (McKay, Piperno, and others), for complexity theorists the problem has been notorious for its unresolved asymptotic worst-case complexity.

In this talk we outline a key combinatorial ingredient of the speaker’s recent algorithm for the problem. A divide-and-conquer approach requires efficient canonical partitioning of graphs and higher-order relational structures. We shall indicate why Johnson graphs are the sole obstructions to this approach. This talk will be purely combinatorial, no familiarity with group theory will be required.

This talk is the keynote of the conference. Hopefully Babai will update us all on the state of this graph isomorphism result. We have discussed here his partial retraction. I am quite interested in seeing what he has to say about the role of Johnson graphs. These were discovered by Selmer Johnson. They are highly special: they are regular, vertex-transitive, distance-transitive, and Hamilton-connected. I find it very interesting that such special graphs seem to be the obstacle to progress on the isomorphism problem.


Petr Hliněný
A Short Proof of Euler-Poincaré Formula

Abstract: We provide a short self-contained inductive proof of famous Euler-Poincaré Formula for the numbers of faces of a convex polytope in every dimension. Our proof is elementary and it does not use shellability of polytopes.

The paper for this talk is remarkably short, only 3 pages. Of course the result has been around since the 1700s and 1800s, and David Eppstein already has a list of 20 proofs of it, so what is the point? It has to do with ways of proving things and the kind of dialogue we can have with ourselves and/or others about what is needed and what won’t work. Imre Lakatos famously codified this process, with this theorem as a running example conjuring up the so-called Lakatosian Monsters. Perhaps the talk will slay the monsters, but it will have to brave some snow and ice first.

Luke Postle
On the List Coloring Version of Reed’s Conjecture

Abstract: In 1998, Reed conjectured that chromatic number of a graph is at most halfway between its trivial lower bound, the clique number, and its trivial upper bound, the maximum degree plus one. Reed also proved that the chromatic number is at most some convex combination of the two bounds. In 2012, King and Reed gave a short proof of this fact. Last year, Bonamy, Perrett and I proved that a fraction of 1/26 away from the upper bound holds for large enough maximum degree. In this talk, we show using new techniques that the list-coloring versions of these results hold, namely that there is such a convex combination for which the statement holds for the list chromatic number. Furthermore, we show that for large enough maximum degree, a fraction of 1/13 suffices for the list chromatic number, improving also on the bound for ordinary chromatic number. This is joint work with Michelle Delcourt.

Mohit Singh
Nash Social Welfare, Permanents and Inequalities on Stable Polynomials

Abstract: Given a collection of items and agents, Nash social welfare problem aims to find a fair assignment of these items to agents. The Nash social welfare objective is to maximize the geometric mean of the valuation of the agents in the assignment. In this talk, we will give a new mathematical programming relaxation for the problem and give an approximation algorithm based on a simple randomized algorithm. To analyze the algorithm, we find new connections of the Nash social welfare problem to the problem of computation of permanent of a matrix. A crucial ingredient in this connection will be new inequalities on stable polynomials that generalize the work of Gurvits. Joint work with Nima Anari, Shayan Oveis-Gharan and Amin Saberi.

Open Problems

There are two. One is, will we be snowed in or snowed out this Monday? The other is, can some of the open problem raised by these talks be solved?

Babai’s Result: Still a Breakthrough

January 4, 2017

Even after today’s retraction of quasi-polynomial time for graph isomorphism

Cropped from source

László Babai is famous for many things, and has made many seminal contributions to complexity theory. Last year he claimed that Graph Isomorphism (GI) is in quasi-polynomial time.

Today Laci posted a retraction of this claim, conceding that the proof has a flaw in the timing analysis, and Ken and I want to make a comment on what is up. Update 1/10: He has posted a 1/9 update reinstating the claim of quasi-polynomial time with a revised algorithm. As we’ve noted, he is currently speaking at Georgia Tech, and we hope to have more information soon.
Read more…

The Gift of Community

December 29, 2016

Shared experience may matter as much as scientific cooperation

AIP source—see also interview

Robert Marshak was on hand for Trinity, which was the first detonation of a nuclear weapon, ever. The test occurred at 5:29 am on July 16, 1945, as part of the Manhattan Project. Marshak was the son of parents who fled pogroms in Byelorussia. Witnessing the test, hearing the destruction of Hiroshima and Nagasaki, and knowing his family history led him to become active in advancing peace. He soon co-founded and chaired the Federation of Atomic Scientists and was active in several other organizations promoting scientific co-operation as a vehicle of world peace. In 1992 he won the inaugural award of the American Association for the Advancement of Science for Science Diplomacy.

Today, the fifth day of both Chanukah and Christmas, we reflect on the gift of international scientific community.
Read more…

Hunting Complexity in Zeta

December 20, 2016

A second look at Voronin’s amazing universality theorem


Anatoly Karatsuba and Sergei Voronin wrote a book on Bernhard Riemann’s zeta function. The book was translated into English by Neal Koblitz in 1992. Among its special content is expanded treatment of an amazing universality theorem about the classic zeta function proved by Voronin in 1975. We covered it four years ago.

Today Ken and I take a second look and explore a possible connection to complexity theory.
Read more…

Bletchley Park

December 12, 2016

Lessons from the Park that still apply today


Iain Standen is the CEO of the Bletchley Park Trust, which is responsible for the restoration of the Park. After the war, the Park was almost completely destroyed and forgotten—partially at least for security reasons. Luckily it was just barely saved and is now a wonderful place to visit and see how such a small place helped change history.

Today I would like to report on a recent trip to Bletchley Park.
Read more…

Magnus and the Turkey Grinder

December 8, 2016

With part II of our “When Data Serves Turkey” post

Baku Olympiad source—note similarity to this

Magnus Carlsen last week retained his title of World Chess Champion. His match against challenger Sergey Karjakin had finished 6–6 after twelve games at “Standard” time controls, but he prevailed 3–1 in a four-game tiebreak series at “Rapid” time controls. Each game took an hour or hour-plus under a budget of 25 minutes plus 10 extra seconds for each move played.

Today we congratulate Carlsen and give the second half of our post on large data being anomalous. Read more…

When Data Serves Turkey

November 30, 2016

A head-scratching inconsistency in large amounts of chess data

Slate source

Benjamin Franklin was the first American scientist and was sometimes called “The First American.” He also admired the American turkey, counter to our connotation of “turkey” as an awkward failure.

Today I wonder what advice Ben would give on an awkward, “frankly shocking,” situation with my large-scale chess data. This post is in two parts.
Read more…