  We study polynomial systems with prescribed monomial supports in the Cox
rings of toric varieties built from complete polyhedral fans. We present
combinatorial formulas for the dimensions of their associated subvarieties
under genericity assumptions on the coefficients of the polynomials. Using
these formulas, we identify at which degrees generic systems in polytopal
algebras form regular sequences. Our motivation comes from sparse elimination
theory, where knowing the expected dimension of these subvarieties leads to
specialized algorithms and to large speed-ups for solving sparse polynomial
systems. As a special case, we classify the degrees at which regular sequences
defined by weighted homogeneous polynomials can be found, answering an open
question in the Gr\"obner bases literature. We also show that deciding whether
a sparse system is generically a regular sequence in a polytopal algebra is
hard from the point of view of theoretical computational complexity.
