language: en

ON THE POWER OF TWO-POINTS BASED SAMPLING

Benny Chor Oded Goldreich flfl
MIT Laboratory for Computer Science
Cambridge, Massachusetts 02139

Abstract | The purpose of this note is to present a new sampling technique and to demonstrate some of its properties. The new technique consists of picking two elements at random, and deterministically generating (from them) a long sequence of pairwise independent elements. The sequence is guarantees to intersect, with high probability, any set of non-negligible density.

1. Introduction