Knutson, Tao, and Woodward introduced puzzle pieces consisting of two triangles and a rhombus (with edge labels). They proved that tilings by these puzzle pieces (allowing rotations) of triangular regions (with edge labels) are counted by Littlewood--Richardson coefficients. These numbers appear naturally in many contexts, including intersection of Schubert varieties, multiplication of Schur functions, and tensor products of irreducible representations of general linear groups.

Together with the saturation conjecture, proved by Knutson and Tao, this means, in particular, that tileability of triangular regions by puzzle pieces can be decided in polynomial time. In this talk, we will discuss the problem of tiling arbitrary regions with these puzzle pieces. Regardless of whether reflections are allowed when tiling, the problem is NP-complete.

(Joint work with Igor Pak.)