  We investigate the distributed complexity of maximal matching and maximal
independent set (MIS) in hypergraphs in the LOCAL model. A maximal matching of
a hypergraph $H=(V_H,E_H)$ is a maximal disjoint set $M\subseteq E_H$ of
hyperedges and an MIS $S\subseteq V_H$ is a maximal set of nodes such that no
hyperedge is fully contained in $S$. Both problems can be solved by a simple
sequential greedy algorithm, which can be implemented naively in $O(\Delta r +
\log^* n)$ rounds, where $\Delta$ is the maximum degree, $r$ is the rank, and
$n$ is the number of nodes.
  We show that for maximal matching, this naive algorithm is optimal in the
following sense. Any deterministic algorithm for solving the problem requires
$\Omega(\min\{\Delta r, \log_{\Delta r} n\})$ rounds, and any randomized one
requires $\Omega(\min\{\Delta r, \log_{\Delta r} \log n\})$ rounds. Hence, for
any algorithm with a complexity of the form $O(f(\Delta, r) + g(n))$, we have
$f(\Delta, r) \in \Omega(\Delta r)$ if $g(n)$ is not too large, and in
particular if $g(n) = \log^* n$ (which is the optimal asymptotic dependency on
$n$ due to Linial's lower bound [FOCS'87]). Our lower bound proof is based on
the round elimination framework, and its structure is inspired by a new round
elimination fixed point that we give for the $\Delta$-vertex coloring problem
in hypergraphs.
  For the MIS problem on hypergraphs, we show that for $\Delta\ll r$, there are
significant improvements over the naive $O(\Delta r + \log^* n)$-round
algorithm. We give two deterministic algorithms for the problem. We show that a
hypergraph MIS can be computed in $O(\Delta^2\cdot\log r + \Delta\cdot\log
r\cdot \log^* r + \log^* n)$ rounds. We further show that at the cost of a
worse dependency on $\Delta$, the dependency on $r$ can be removed almost
entirely, by giving an algorithm with complexity $\Delta^{O(\Delta)}\cdot\log^*
r + O(\log^* n)$.
