Peak algebras, paths in the Bruhat graph and Kazhdan-Lusztig polynomials

We give a new characterization of the peak subalgebra of the algebra of quasisymmetric functions and use this to construct a new basis for this subalgebra. As an application of these results we obtain a combinatorial formula for the Kazhdan-Lusztig polynomials which holds in complete generality and is simpler and more explicit than any existing one. We then show that, in a certain sense, this formula cannot be simplified.