  We define new deformations of group algebras of Coxeter groups W and of
subgroups of even elements in them, by deforming the braid relations. We show
that these deformations are algebraically flat iff they are formally flat, and
that this happens iff the group W has no finite parabolic subgroups of rank 3.
The proof uses the theory of constructible sheaves on cell complexes attached
to W. We explain the connection of our deformations with the Hecke algebras of
orbifolds defined by the first author in math.QA/0406499 and with generalized
double affine Hecke algebras defined by the authors and A. Oblomkov in
math.QA/0406480. The paper is dedicated to the memory of Walter Feit.
