Local Access to Huge Random Objects through Partial Sampling. Consider an algorithm performing a computation on a huge random object. Is it necessary to generate the entire object up front, or is it possible to provide query access to the object and sample it incrementally onthefly? Such an implementation should emulate the object by answering queries in a manner consistent with a random instance sampled from the true distribution.  Our first set of results focus on undirected graphs with independent edge probabilities, under certain assumptions. Then, we use this to obtain the first efficient implementations for the ErdosRenyi model and the Stochastic Block model. As in previous localaccess implementations for random graphs, we support VertexPair and NextNeighbor queries. We also introduce a new RandomNeighbor query.  Next, we show how to implement random Catalan objects, specifically focusing on Dyck paths (always positive random walks on the integer line). Here, we support Height queries to find the position of the walk, and FirstReturn queries to find the time when the walk returns to a specified height. This in turn can be used to implement NextNeighbor queries on random rootedbinary trees, and MatchingBracket queries on random well bracketed expressions.  Finally, we define a new model that: (1) allows multiple independent simultaneous instantiations of the same implementation to be consistent with each other without communication (2) allows us to generate a richer class of random objects that do not have a succinct description. Specifically, we study uniformly random valid qcolorings of an input graph G with max degree Delta. The distribution over valid colorings is specified via a huge underlying graph G, that is far too large to be read in sublinear time. Instead, we access G through local neighborhood probes. We are able to answer queries to the color of any vertex in sublinear time for q u003e 9Delta.

Small Cuts and Connectivity Certificates: A Fault Tolerant Approach We revisit classical connectivity problems in the CONGEST model of distributed computing. By using techniques from fault tolerant network design, we show improved constructions, some of which are even local (i.e., with widetildeO(1) rounds) for problems that are closely related to hard global problems (i.e., with a lower bound of Omega(Diamsqrtn) rounds).  :52,main results are:  :56,For Ddiameter unweighted graphs with constant edge connectivity, we show an exact distributed deterministic computation of the minimum cut in poly(D) rounds. This resolves one the open problems recently raised in Daga, Henzinger, Nanongkai and Saranurak, STOCu002719.  :56,For Ddiameter unweighted :94,graphs, we present a deterministic algorithm that computes of all edge connectivities up to constant in poly(D)cdot 2O(sqrtlog nloglog n) rounds.  :119,Computation of sparse lambda connectivity certificates in widetildeO(lambda) rounds. Previous constructions where known only for lambda leq 3 and required O(D) rounds. This resolves the problem raised by Dori PODCu002718.