My understanding is that Soergel's approach applies just to finite Weyl groups and not directly to other finite Coxeter groups (or more generally), since what he can actually prove depends on some of the geometric machinery used to prove the Kazhdan-Lusztig Conjecture. The same must be true of the 1999 thesis work of his student Martin Harterich involving affine Weyl groups, which doesn't seem to have been formally published. In those situations the coefficients of KL polynomials were seen to be nonnegative in the early steps taken by Kazhdan and Lusztig toward understanding their conjecture via Schubert varieties: they occur as dimensions of certain cohomology groups.

Later on, Soergel made his program more explicit for proving the nonnegativity for arbitrary Coxeter groups using his more algebraic/categorical setting of bimodules: MR2329762 (2009c:20009) 20C08 (20F55) Soergel,Wolfgang (D-FRBG), Kazhdan-Lusztig-Polynome und unzerlegbare Bimoduln ¨uber Polynomringen. (German. English, German summaries) [Kazhdan-Lusztig polynomials and indecomposable bimodules over polynomial rings] J. Inst. Math. Jussieu 6 (2007), no. 3, 501–525. This is in a French journal but written in German; the helpful review by Ulrich Goertz is however in English if you have access to MathSciNet. (In any case, J. Reine Angew. Math. has become super-expensive for libraries, so print or online access gets tricky.)

A helpful follow-up paper (in English) by Soergel's later student Peter Fiebig (now at Erlangen) should also be consulted, though it is still unclear to me how far one can get with Soergel's conjectural approach in this spirit: MR2395170 (2009g:20087) 20F55 (20C08) Fiebig, Peter (D-FRBG), The combinatorics of Coxeter categories. Trans. Amer. Math. Soc. 360 (2008), no. 8, 4211–4233.

I'll have to take another look at this literature, but in any case the nonnegativity of coefficients of KL polynomials for arbitrary Coxeter groups (predicted in 1979 by Kazhdan and Lusztig) remains an intriguing question. The general setting is far from the kind of representation theory or geometry one encounters in Lie theory, but a purely combinatorial approach seems at the moment unlikely to succeed.

ADDED: Special cases where Kazhdan-Lusztig polynomials have been computed are discussed in section 7.12 of my 1990/1992 book on reflection groups and Coxeter groups. In particular, noncrystallographic finite Coxeter groups all yield nonnegative coefficients. For dihedral groups, the polynomials are all 1, while for type $H_3$ the computer tables found by Mark Goresky are still on his Webpage at IAS. The 1987 paper in J. Algebra by Dean Alvis which I cited involved his unpublished computer results on the polynomials for $H_4$, for which his current Webpage gives details: http://mypage.iusb.edu/~dalvis/h4data/index.html

These polynomials were later recovered by Fokko du Cloux using his computer system Coxeter: see his last published paper MR2255133 (2007e:20010) 20C08 (20F55) du Cloux, Fokko (F-LYON-ICJ), Positivity results for the Hecke algebras of noncrystallographic finite Coxeter groups. J. Algebra 303 (2006), no. 2, 731–741.

My understanding is that Soergel's approach applies just to finite Weyl groups and not directly to other finite Coxeter groups (or more generally), since what he can actually prove depends on some of the geometric machinery used to prove the Kazhdan-Lusztig Conjecture. The same must be true of the 1999 thesis work of his student Martin Harterich involving affine Weyl groups, which doesn't seem to have been formally published. In those situations the coefficients of KL polynomials were seen to be nonnegative in the early steps taken by Kazhdan and Lusztig toward understanding their conjecture via Schubert varieties: they occur as dimensions of certain cohomology groups.

Later on, Soergel made his program more explicit for proving the nonnegativity for arbitrary Coxeter groups using his more algebraic/categorical setting of bimodules: MR2329762 (2009c:20009) 20C08 (20F55) Soergel,Wolfgang (D-FRBG), Kazhdan-Lusztig-Polynome und unzerlegbare Bimoduln ¨uber Polynomringen. (German. English, German summaries) [Kazhdan-Lusztig polynomials and indecomposable bimodules over polynomial rings] J. Inst. Math. Jussieu 6 (2007), no. 3, 501–525. This is in a French journal but written in German; the helpful review by Ulrich Goertz is however in English if you have access to MathSciNet. (In any case, J. Reine Angew. Math. has become super-expensive for libraries, so print or online access gets tricky.)

A helpful follow-up paper (in English) by Soergel's later student Peter Fiebig (now at Erlangen) should also be consulted, though it is still unclear to me how far one can get with Soergel's conjectural approach in this spirit: MR2395170 (2009g:20087) 20F55 (20C08) Fiebig, Peter (D-FRBG), The combinatorics of Coxeter categories. Trans. Amer. Math. Soc. 360 (2008), no. 8, 4211–4233. (Fiebig's papers are on arXiv, by the way.)

I'll have to take another look at this literature, but in any case the nonnegativity of coefficients of KL polynomials for arbitrary Coxeter groups (predicted in 1979 by Kazhdan and Lusztig) remains an intriguing question. The general setting is far from the kind of representation theory or geometry one encounters in Lie theory, but a purely combinatorial approach seems at the moment unlikely to succeed.

ADDED: Special cases where Kazhdan-Lusztig polynomials have been computed are discussed in section 7.12 of my 1990/1992 book on reflection groups and Coxeter groups. In particular, noncrystallographic finite Coxeter groups all yield nonnegative coefficients. For dihedral groups, the polynomials are all 1, while for type $H_3$ the computer tables found by Mark Goresky are still on his Webpage at IAS. The 1987 paper in J. Algebra by Dean Alvis which I cited involved his unpublished computer results on the polynomials for $H_4$, for which his current Webpage gives details: http://mypage.iusb.edu/~dalvis/h4data/index.html

These polynomials were later recovered by Fokko du Cloux using his computer system Coxeter: see his last published paper MR2255133 (2007e:20010) 20C08 (20F55) du Cloux, Fokko (F-LYON-ICJ), Positivity results for the Hecke algebras of noncrystallographic finite Coxeter groups. J. Algebra 303 (2006), no. 2, 731–741.

My understanding is that Soergel's approach applies just to finite Weyl groups and not directly to other finite Coxeter groups (or more generally), since what he can actually prove depends on some of the geometric machinery used to prove the Kazhdan-Lusztig Conjecture. The same must be true of the 1999 thesis work of his student Martin Harterich involving affine Weyl groups, which doesn't seem to have been formally published. In those situations the coefficients of KL polynomials were seen to be nonnegative in the early steps taken by Kazhdan and Lusztig toward understanding their conjecture via Schubert varieties: they occur as dimensions of certain cohomology groups.

Later on, Soergel made his program more explicit for proving the nonnegativity for arbitrary Coxeter groups using his more algebraic/categorical setting of bimodules: MR2329762 (2009c:20009) 20C08 (20F55) Soergel,Wolfgang (D-FRBG), Kazhdan-Lusztig-Polynome und unzerlegbare Bimoduln ¨uber Polynomringen. (German. English, German summaries) [Kazhdan-Lusztig polynomials and indecomposable bimodules over polynomial rings] J. Inst. Math. Jussieu 6 (2007), no. 3, 501–525. This is in a French journal but written in German; the helpful review by Ulrich Goertz is however in English if you have access to MathSciNet. (In any case, J. Reine Angew. Math. has become super-expensive for libraries, so print or online access gets tricky.)

A helpful follow-up paper (in English) by Soergel's later student Peter Fiebig (now at Erlangen) should also be consulted, though it is still unclear to me how far one can get with Soergel's conjectural approach in this spirit: MR2395170 (2009g:20087) 20F55 (20C08) Fiebig, Peter (D-FRBG), The combinatorics of Coxeter categories. Trans. Amer. Math. Soc. 360 (2008), no. 8, 4211–4233.

I'll have to take another look at this literature, but in any case the nonnegativity of coefficients of KL polynomials for arbitrary Coxeter groups (predicted in 1979 by Kazhdan and Lusztig) remains an intriguing question. The general setting is far from the kind of representation theory or geometry one encounters in Lie theory, but a purely combinatorial approach seems at the moment unlikely to succeed.

My understanding is that Soergel's approach applies just to finite Weyl groups and not directly to other finite Coxeter groups (or more generally), since what he can actually prove depends on some of the geometric machinery used to prove the Kazhdan-Lusztig Conjecture. The same must be true of the 1999 thesis work of his student Martin Harterich involving affine Weyl groups, which doesn't seem to have been formally published. In those situations the coefficients of KL polynomials were seen to be nonnegative in the early steps taken by Kazhdan and Lusztig toward understanding their conjecture via Schubert varieties: they occur as dimensions of certain cohomology groups.

Later on, Soergel made his program more explicit for proving the nonnegativity for arbitrary Coxeter groups using his more algebraic/categorical setting of bimodules: MR2329762 (2009c:20009) 20C08 (20F55) Soergel,Wolfgang (D-FRBG), Kazhdan-Lusztig-Polynome und unzerlegbare Bimoduln ¨uber Polynomringen. (German. English, German summaries) [Kazhdan-Lusztig polynomials and indecomposable bimodules over polynomial rings] J. Inst. Math. Jussieu 6 (2007), no. 3, 501–525. This is in a French journal but written in German; the helpful review by Ulrich Goertz is however in English if you have access to MathSciNet. (In any case, J. Reine Angew. Math. has become super-expensive for libraries, so print or online access gets tricky.)

A helpful follow-up paper (in English) by Soergel's later student Peter Fiebig (now at Erlangen) should also be consulted, though it is still unclear to me how far one can get with Soergel's conjectural approach in this spirit: MR2395170 (2009g:20087) 20F55 (20C08) Fiebig, Peter (D-FRBG), The combinatorics of Coxeter categories. Trans. Amer. Math. Soc. 360 (2008), no. 8, 4211–4233.

I'll have to take another look at this literature, but in any case the nonnegativity of coefficients of KL polynomials for arbitrary Coxeter groups (predicted in 1979 by Kazhdan and Lusztig) remains an intriguing question. The general setting is far from the kind of representation theory or geometry one encounters in Lie theory, but a purely combinatorial approach seems at the moment unlikely to succeed.

ADDED: Special cases where Kazhdan-Lusztig polynomials have been computed are discussed in section 7.12 of my 1990/1992 book on reflection groups and Coxeter groups. In particular, noncrystallographic finite Coxeter groups all yield nonnegative coefficients. For dihedral groups, the polynomials are all 1, while for type $H_3$ the computer tables found by Mark Goresky are still on his Webpage at IAS. The 1987 paper in J. Algebra by Dean Alvis which I cited involved his unpublished computer results on the polynomials for $H_4$, for which his current Webpage gives details: http://mypage.iusb.edu/~dalvis/h4data/index.html

These polynomials were later recovered by Fokko du Cloux using his computer system Coxeter: see his last published paper MR2255133 (2007e:20010) 20C08 (20F55) du Cloux, Fokko (F-LYON-ICJ), Positivity results for the Hecke algebras of noncrystallographic finite Coxeter groups. J. Algebra 303 (2006), no. 2, 731–741.