  We show that the largest density of factor of i.i.d. independent sets on the
d-regular tree is asymptotically at most (log d)/d as d tends to infinity. This
matches the lower bound given by previous constructions. It follows that the
largest independent sets given by local algorithms on random d-regular graphs
have the same asymptotic density. In contrast, the density of the largest
independent sets on these graphs is asymptotically 2(log d)/d. We also prove
analogous results for Poisson-Galton-Watson trees, which yield bounds for local
algorithms on sparse Erdos-Renyi graphs.
