On the Complexity of Parity Word Automata Different types of nondeterministic automata on infinite words differ in their succinctness and in the complexity for their nonemptiness problem. A simple translation of a parity automaton to an equivalent \buchi automaton is quadratic: a parity automaton with $n$ states, $m$ transitions, and index $k$ may result in a \buchi automaton of size $O((n+m)k)$. The best algorithm known for the nonemptiness problem of parity automata goes through \buchi automata, leading to a complexity of $O((n+m)k)$. In this paper we show that while the translation of parity automata to \buchi automata cannot be improved, the special structure of the acceptance condition of parity automata can be used in order to solve the nonemptiness problem directly, with a dynamic graph algorithm of complexity $O((n+m) \log k)$.