All reports by Author Eliran Kachlon:

__
TR19-011
| 27th January 2019
__

Benny Applebaum, Eliran Kachlon#### Sampling Graphs without Forbidden Subgraphs and Almost-Explicit Unbalanced Expanders

Benny Applebaum, Eliran Kachlon

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