Revision #2 Authors: Benny Applebaum, Eliran Kachlon

Accepted on: 22nd September 2019 11:10

Downloads: 667

Keywords:

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).

Revision #1 Authors: Benny Applebaum, Eliran Kachlon

Accepted on: 22nd September 2019 10:51

Downloads: 620

Keywords:

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).

TR19-011 Authors: Benny Applebaum, Eliran Kachlon

Publication: 27th January 2019 19:16

Downloads: 1164

Keywords:

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.