Suppose that you wish to sample a random graph G over n vertices and m edges conditioned on the event that G does not contain a ``small'' t -size graph H (e.g., clique) as a subgraph. Assuming that most such graphs are H -free, the problem can be solved by a simple rejected-sampling algorithm (that tests for t -cliques) with an expected running time of n O ( t ) . Is it possible to solve the problem in running time that does not grow polynomially with n t ?

In this paper, we introduce the general problem of sampling a ``random looking'' graph G with a given edge density that avoids some arbitrary predefined t -size subgraph H . As our main result, we show that the problem is solvable with respect to some specially crafted k -wise independent distribution over graphs. That is, we design a sampling algorithm for k -wise independent graphs that supports efficient testing for subgraph-freeness in time f ( t ) n c where f is a function of t and the constant c in the exponent is independent of t . Our solution extends to the case where both G and H are d -uniform hypergraphs.

We use these algorithms to obtain the first probabilistic construction of constant-degree polynomially-unbalanced expander graphs whose failure probability is \emph{negligible} in n (i.e., n − (1) ). In particular, given constants c"> d c , we output a bipartite graph that has n left nodes, n c right nodes with right-degree of d so that any right set of size at most n (1) expands by factor of ( d ) . This result is extended to the setting of unique expansion as well.

We observe that such a negligible-error construction can be employed in many useful settings, and present applications in coding theory (batch codes and LDPC codes), pseudorandomness (low-bias generators and randomness extractors) and cryptography. Notably, we show that our constructions yield a collection of polynomial-stretch locally-computable cryptographic pseudorandom generators based on Goldreich's one-wayness assumption resolving a central open problem in parallel-cryptography (cf., Applebaum-Ishai-Kushilevitz, FOCS 2004; and Ishai-Kushilevitz-Ostrovsky-Sahai, STOC 2008).