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)\cdot 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 negligible in $n$ (i.e., $n^{-\omega(1)}$). In particular, given constants $d>c\geq 1$, 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^{\Omega(1)}$ expands by factor of $\Omega(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 the area of parallel-time cryptography (e.g., Applebaum-Ishai-Kushilevitz, FOCS 2004; and Ishai-Kushilevitz-Ostrovsky-Sahai, STOC 2008).

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)\cdot 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^{-\omega(1)}$). In particular, given constants $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^{\Omega(1)}$ expands by factor of $\Omega(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).

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)\cdot 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^{-\omega(1)}$). In particular, given constants $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^{\Omega(1)}$ expands by factor of $\Omega(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).

We initiate the study of the following hypergraph sampling problem: Sample a $d$-uniform hypergraph over $n$ vertices and $m$ hyperedges from some pseudorandom distribution $\mathcal{G}$ conditioned on not having some small predefined $t$-size hypergraph $H$ as a subgraph. The algorithm should run in $\mathrm{poly}(n)$-time even when the size of the subgraph $H$ is super-constant.

We solve the problem by carefully designing a sampling algorithm for $k$-wise independent hypergraphs $\mathcal{G}$ that supports efficient testing for subgraph-freeness. We use our algorithm to obtain the first probabilistic construction of constant-degree polynomially-unbalanced expander graphs whose failure probability is negligible in $n$ (i.e., $n^{-\omega(1)}$). In particular, given constants $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^{\Omega(1)}$ expands by factor of $\Omega(d)$. This result is extended to the setting of unique expansion as well.

We argue that such an ``almost-explicit'' 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 long-standing open problem.