In many real world applications we have only limited access to networks. For example when we crawl a social network or we design a peer-to-peer system we are restricted to access nodes only locally. In this talk we will analyze two classic problems in this setting. First we consider the problem of sampling nodes from a large graph according to a prescribed distribution by using only local random walks as the basic primitive. Our goal is to obtain algorithms that make a small number of queries to the graph but output a node that is sampled according to the prescribed distribution. Focusing on the uniform distribution case, we study the query complexity of three algorithms and show a near-tight bound expressed in terms of the parameters of the graph such as average degree and the mixing time. Both theoretically and empirically, we show that some algorithms are preferable in practice than the others. We also extend our study to the problem of sampling nodes according to some polynomial function of their degrees; this has implications for designing efficient algorithms for applications such as triangle counting. Then we focus on the following classic distributed problem with applications to peer-to-peer networks. Given an n-node d-regular network for d = Ω(log n), we want to design a decentralized, local algorithm that transforms the graph into one that has good connectivity properties (low diameter, expansion, etc.) without affecting the sparsity of the graph. To this end, Mahlmann and Schindelhauer introduced the random “flip” transformation, where in each time step, a random pair of vertices that have an edge decide to ‘swap a neighbor’. They conjectured that performing O(nd) such flips at random would convert any connected d-regular graph into a d-regular expander graph, with high probability. However, the best known upper bound for the number of steps is roughly O(n^17d^23), obtained via a delicate Markov chain comparison argument. Our main result is to prove that a natural instantiation of the random flip produces an expander in at most O(n^2d^2\sqrt{log n}) steps, with high probability. We also show that our technique can be used to analyze another well-studied random process known as the ‘random switch’, and show that it produces an expander in O(nd) steps with high probability. (Joint work with Zeyuan Allen-Zhu, Aditya Bhaskara, Flavio Chierichetti, Anirban Dasgupta, Ravi Kumar, Lorenzo Orecchia and Tamas Sarlos)