  Kazhdan-Lusztig polynomials are important and mysterious objects in
representation theory. Here we present a new formula for their computation for
symmetric groups based on the Bruhat graph. Our approach suggests a solution to
the combinatorial invariance conjecture for symmetric groups, a well-known
conjecture formulated by Lusztig and Dyer in the 1980s.
