**Abstract:**
We prove that the set of properties describable by a uniform sequence of
first-order sentences using at most k+1 distinct
variables is exactly equal to
the set of properties checkable
by a Turing machine in DSPACE[n^{k}] (where n is the size of the
universe).
This set is also equal to the set of
properties describable using an iterative definition for a
finite set of relations of arity k. This is a refinement
of the theorem PSPACE = VAR[O(1)], [Imm82]. We suggest some directions for exploiting this
result to derive trade-offs between the number of variables
and the quantifier depth in descriptive complexity.

Recent Publications of Neil Immerman