## Sampling Graphs without Forbidden Subgraphs
and Almost-Explicit Unbalanced Expanders

by Benny Applebaum and Eliran Kachlon

#### Oded's comments

This is a very impressive work.
One if its contributions is resolving the problem of constructing
pseudorandom generators with arbitrary polynomial stretch in NC0
based on the one-wayness of a similar construct.
Another is introducing and solving problems that related to
sampling a graph with a specified number of vertices and edges
uniformly at random conditioned on not having a copy of a
specified (small) graph as a subgraph, where the sampler is required to
work significantly faster than the time required to check all relevant-sized
subsets of the vertex set.

Unfortunately, the write-up is quite imposing,
making it quite a challenge to figure out
what is actually being achieved and how.
It seems that the problem is not a lack of desire
to clearly communicate the contents of the work,
but rather a desire to communicate all of it.

#### The original abstract

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.

See ECCC TR19-011.

Back to
list of Oded's choices.