Let $G$ be a reductive group over the field $F=k((t))$, where $k$ is an algebraic closure of a finite field, and let $W$ be the (extended) affine Weyl group of $G$. The associated affine Deligne-Lusztig varieties $X_x(b)$, which are indexed by elements $b \in G(F)$ and $x \in W$, were introduced by Rapoport. Basic questions about the varieties $X_x(b)$ which have remained largely open include when they are nonempty, and if nonempty, their dimension...