ECCC-Report TR19-011https://eccc.weizmann.ac.il/report/2019/011Comments and Revisions published for TR19-011en-usSun, 22 Sep 2019 11:10:40 +0300
Revision 2
| Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error |
Benny Applebaum,
Eliran Kachlon
https://eccc.weizmann.ac.il/report/2019/011#revision2Suppose 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).Sun, 22 Sep 2019 11:10:40 +0300https://eccc.weizmann.ac.il/report/2019/011#revision2
Revision 1
| Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error |
Benny Applebaum,
Eliran Kachlon
https://eccc.weizmann.ac.il/report/2019/011#revision1Suppose 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).Sun, 22 Sep 2019 10:51:48 +0300https://eccc.weizmann.ac.il/report/2019/011#revision1
Paper TR19-011
| Sampling Graphs without Forbidden Subgraphs and Almost-Explicit Unbalanced Expanders |
Benny Applebaum,
Eliran Kachlon
https://eccc.weizmann.ac.il/report/2019/011We 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.
Sun, 27 Jan 2019 19:16:23 +0200https://eccc.weizmann.ac.il/report/2019/011