  A parallel algorithm for maximal independent set (MIS) in hypergraphs has
been a long-standing algorithmic challenge, dating back nearly 30 years to a
survey of Karp & Ramachandran (1990). The best randomized parallel algorithm
for hypergraphs of fixed rank $r$ was developed by Beame & Luby (1990) and
Kelsen (1992), running in time roughly $(\log n)^{r!}$.
  We improve the randomized algorithm of Kelsen, reducing the runtime to
roughly $(\log n)^{2^r}$ and simplifying the analysis through the use of
more-modern concentration inequalities. We also give a method for derandomizing
concentration bounds for low-degree polynomials, which are the key technical
tool used to analyze that algorithm. This leads to a deterministic PRAM
algorithm also running in $(\log n)^{2^{r+3}}$ time and $\text{poly}(m,n)$
processors. This is the first deterministic algorithm with sub-polynomial
runtime for hypergraphs of rank $r > 3$.
  Our analysis can also apply when $r$ is slowly growing; using this in
conjunction with a strategy of Bercea et al. (2015) gives a deterministic MIS
algorithm running in time $\exp(O( \frac{\log (mn)}{\log \log (mn)}))$.
