Bounded-Independence Sampling of Edges for Combinatorial Graph Properties

Aaron Putterman, Salil Vadhan, Vadim Zaripov

Random subsampling of edges is a commonly employed technique in graph algorithms, underlying a vast array of modern algorithmic breakthroughs. Unfortunately, using this technique o…