Lattice paths, lexicographic correspondence and Kazhdan–Lusztig polynomials

In this paper we give a new closed formula for the Kazhdan–Lusztig polynomials of finite Coxeter groups and affine Weyl groups. This formula is computationally more efficient than any existing one, and it conjecturally holds for all Coxeter groups.