  The paper deals with extremal problems concerning colorings of hypergraphs.
By using a random recoloring algorithm we show that any $n$-uniform simple
(i.e. every two distinct edges share at most one vertex) hypergraph $H$ with
maximum edge degree at most \[
  \Delta(H)\leq c\cdot nr^{n-1}, \] is $r$-colorable, where $c>0$ is an
absolute constant. %We prove also that similar result holds for $b$-simple
hypergraphs.
  As an application of our proof technique we establish a new lower bound for
Van der Waerden number $W(n,r)$, the minimum $N$ such that in any $r$-coloring
of the set $\{1,...,N\}$ there exists a monochromatic arithmetic progression of
length $n$. We show that \[
  W(n,r)>c\cdot r^{n-1}, \] for some absolute constant $c>0$.

Combinatorics;Discrete Mathematics