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.