ABSTRACT
Two-point sampling, an alternative technique developed by Chor and Goldreich [496], is amenable to more realistic implementation and analysis. This technique essentially uses orthogonal arrays. Suppose logn random bits are needed for one trial of the algorithm and k trials of the algorithm are to be conducted. Instead of generating k logn random bits, which would ensure independence, one can use orthogonal arrays to generate pairwise independent random numbers as follows. Consider any OA(2, k, n). This array has n2 rows. Generate 2 logn random bits and use them to index a specific row of the OA. Now apply the Monte Carlo algorithm using the k points that are elements of the row selected. By elementary combinatorial arguments
[931], the probability of getting k “no” answers for a yes-instance is bounded above by
1+(k−1)(1−).
