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

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