In this paper we consider the problem of deciding whether a given $r$-uniform hypergraph $H$ with minimum vertex degree at least $c\binom{|V(H)|-1}{r-1},$ or minimum degree of a pair of vertices at least $c\binom{|V(H)|-2}{r-2}$, has a vertex $2$-coloring. Motivated by an old result of Edwards for graphs, we obtain first optimal dichotomy results for 2-colorings of $r$-uniform hypergraphs. For each problem, for every $r\geq 3$ we determine a threshold value depending on $r$ such that the problem is NP-complete for $c$ below the threshold, while for $c$ strictly above the threshold it is polynomial. We provide an algorithm constructing the coloring with time complexity $O(n^{\lfloor 4/\epsilon\rfloor+2}\log n)$ with some $\epsilon>0.$ This algorithm becomes more efficient in the case of $r=3,4,5$ due to known Tur\'{a}n numbers of the triangle and the Fano plane. In addition, we determine the computational complexity of strong $k$-coloring of 3-uniform hypergraphs $H$ with minimum vertex degree at least $c\binom{|V(H)|-1}{2},$ for some $c,$ leaving a gap for $k\geq 5$ which vanishes as $k\rightarrow \infty$.