  The Local Computation Algorithms (LCA) model is a computational model aimed
at problem instances with huge inputs and output. For graph problems, the input
graph is accessed using probes: strong probes (SP) specify a vertex $v$ and
receive as a reply a list of $v$'s neighbors, and weak probes (WP) specify a
vertex $v$ and a port number $i$ and receive as a reply $v$'s $i^{th}$
neighbor. Given a local query (e.g., "is a certain vertex in the vertex cover
of the input graph?"), an LCA should compute the corresponding local output
(e.g., "yes" or "no") while making only a small number of probes, with the
requirement that all local outputs form a single global solution (e.g., a legal
vertex cover). We study the probe complexity of LCAs that are required to work
on graphs that may have arbitrarily large degrees. In particular, such LCAs are
expected to probe the graph a number of times that is significantly smaller
than the maximum, average, or even minimum degree.
  For weak probes, we focus on the weak coloring problem. Among our results we
show a separation between weak 3-coloring and weak 2-coloring for deterministic
LCAs: $\log^* n + O(1)$ weak probes suffice for weak 3-coloring, but
$\Omega\left(\frac{\log n}{\log\log n}\right)$ weak probes are required for
weak 2-coloring.
  For strong probes, we consider randomized LCAs for vertex cover and
maximal/maximum matching. Our negative results include showing that there are
graphs for which finding a \emph{maximal} matching requires $\Omega(\sqrt{n})$
strong probes. On the positive side, we design a randomized LCA that finds a
$(1-\epsilon)$ approximation to \emph{maximum} matching in regular graphs, and
uses $\frac{1}{\epsilon }^{O\left( \frac{1}{\epsilon ^2}\right)}$ probes,
independently of the number of vertices and of their degrees.
