  We define and study generalized nil-Coxeter algebras associated to Coxeter
groups. Motivated by a question of Coxeter (1957), we construct the first
examples of such finite-dimensional algebras that are not the 'usual'
nil-Coxeter algebras: a novel 2-parameter type $A$ family that we call
$NC_A(n,d)$. We explore several combinatorial properties of $NC_A(n,d)$,
including its Coxeter word basis, length function, and Hilbert-Poincare series,
and show that the corresponding generalized Coxeter group is not a flat
deformation of $NC_A(n,d)$. These algebras yield symmetric semigroup module
categories that are necessarily not monoidal; we write down their Tannaka-Krein
duality.
  Further motivated by the Broue-Malle-Rouquier (BMR) freeness conjecture [J.
reine angew. math. 1998], we define generalized nil-Coxeter algebras over all
discrete real or complex reflection groups $W$, finite or infinite. We provide
a complete classification of all such algebras that are finite-dimensional.
Remarkably, these turn out to be either the usual nil-Coxeter algebras, or the
algebras $NC_A(n,d)$. This proves as a special case - and strengthens - the
lack of equidimensional nil-Coxeter analogues for finite complex reflection
groups. In particular, generic Hecke algebras are not flat deformations of
$NC_W$ for $W$ complex.
