On the power of two-point based sampling

✍ Scribed by Benny Chor; Oded Goldreich

• Publisher: Elsevier Science
• Year: 1989
• Tongue: English
• Weight: 612 KB
• Volume: 5
• Category: Article
• ISSN: 0885-064X
• DOI: 10.1016/0885-064x(89)90015-0

✦ Synopsis

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 guaranteed to intersect, with high probability, any set of non-negligible density. o 1989 Academic PRSS, IX