Monthly Archives: June 2014

Counting Edge Colorings Is Hard

Holants, Galois theorem, complexity dichotomy… Something extremely nice, and something we must learn.

Gödel's Lost Letter and P=NP


Jin-Yi Cai is one of the world’s experts on hardness of counting problems, especially those related to methods based on complex—pun intended—gadgets. He and his students have built a great theory of dichotomy, which we covered two years ago. This means giving conditions under which a counting problem in $latex {mathsf{#P}}&fg=000000$ must either be in $latex {mathsf{P}}&fg=000000$ or be $latex {mathsf{#P}}&fg=000000$-complete, with no possibility in-between. The theory is built around a combinatorial algebraic quantity called the holant, which arose in Leslie Valiant’s theory of holographic algorithms.

Today Ken and I wish to discuss a recent paper on the hardness of counting the number of edge colorings, even for planar graphs.

This work is due to our dear friend Jin-Yi—who has been a colleague of each of us—with Heng Guo and Tyson Williams. It is entitled The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher…

View original post 1,308 more words