Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR19-011 | 27th January 2019 08:17

Sampling Graphs without Forbidden Subgraphs and Almost-Explicit Unbalanced Expanders


Authors: Benny Applebaum, Eliran Kachlon
Publication: 27th January 2019 19:16
Downloads: 116


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.

ISSN 1433-8092 | Imprint