Sampling Independent Set undirected graph G(V,E)of max-degree A Sample (nearly)uniform random independent set. ●△≤5→poly-time Conjecture:O(n log n)time ●△≥6→NP.hardSampling Independent Set • Sample (nearly) uniform random independent set. • Δ ≤ 5 㱺 poly-time Conjecture: O(n log n) time • Δ ≥ 6 㱺 NP-hard undirected graph G(V, E) of max-degree Δ