  Maximal independent set (MIS), maximal matching (MM), and
$(\Delta+1)$-coloring in graphs of maximum degree $\Delta$ are among the most
prominent algorithmic graph theory problems. They are all solvable by a simple
linear-time greedy algorithm and up until very recently this constituted the
state-of-the-art. In SODA 2019, Assadi, Chen, and Khanna gave a randomized
algorithm for $(\Delta+1)$-coloring that runs in $\widetilde{O}(n\sqrt{n})$
time, which even for moderately dense graphs is sublinear in the input size.
The work of Assadi et al. however contained a spoiler for MIS and MM: neither
problems provably admits a sublinear-time algorithm in general graphs. In this
work, we dig deeper into the possibility of achieving sublinear-time algorithms
for MIS and MM.
  The neighborhood independence number of a graph $G$, denoted by $\beta(G)$,
is the size of the largest independent set in the neighborhood of any vertex.
We identify $\beta(G)$ as the ``right'' parameter to measure the runtime of MIS
and MM algorithms: Although graphs of bounded neighborhood independence may be
very dense (clique is one example), we prove that carefully chosen variants of
greedy algorithms for MIS and MM run in $O(n\beta(G))$ and
$O(n\log{n}\cdot\beta(G))$ time respectively on any $n$-vertex graph $G$. We
complement this positive result by observing that a simple extension of the
lower bound of Assadi et.al. implies that $\Omega(n\beta(G))$ time is also
necessary for any algorithm to either problem for all values of $\beta(G)$ from
$1$ to $\Theta(n)$. We note that our algorithm for MIS is deterministic while
for MM we use randomization which we prove is unavoidable: any deterministic
algorithm for MM requires $\Omega(n^2)$ time even for $\beta(G) = 2$.
