zbMATH — the first resource for mathematics

On the power of two-point based sampling. (English) Zbl 0672.60105
Summary: 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.

60K99 Special processes
68U20 Simulation (MSC2010)
Full Text: DOI
[1] Ajtai, M; Wigderson, A, Deterministic simulation of probabilistic constant depth circuits, (), 11-19
[2] Alexi, W; Chor, B; Goldreich, O; Schnorr, C.P; Alexi, W; Chor, B; Goldreich, O; Schnorr, C.P, RSA and rabin functions: certain parts are as hard as the whole, (), 17, 2, 449-457, (1984), preliminary version in
[3] Alon, N, Eigenvalues and expanders, Combinatorica, 6, 2, 83-96, (1986) · Zbl 0661.05053
[4] {\scAlon, N.} (1985), private communication.
[5] Alon, N; Babai, L; Itai, A, A fast and simple randomized parallel algorithm for the maximal independent set problem, J. algorithms, (1986), to appear · Zbl 0631.68063
[6] {\scAnderson, R.} (1985), Set Splitting, manuscript.
[7] Blum, M; Micali, S, How to generate cryptographically strong sequences of pseudo-random bits, SIAM J. comput., 13, 4, 850-864, (1984) · Zbl 0547.68046
[8] Carter, J; Wegman, M, Universal classes of hash functions, J. comput. system sci., 18, 143-154, (1979) · Zbl 0412.68090
[9] Chor, B; Friedman, G; Goldreich, O; Hastad, J; Rudich, S; Smolanski, R, The bit extraction problem or t-resilient functions, (), 396-407
[10] Chor, B; Goldreich, O, RSA/rabin least significant bits are \(12 + 1/ poly( log N)\) secure, Mit/lcs/tm-260, (1984)
[11] Feller, W, ()
[12] Joffe, A, On a sequence of almost deterministic pairwise independent random variables, (), 381-382 · Zbl 0217.21102
[13] Joffe, A, On a set of almost deterministic k-independent random variables, Ann. probab., 2, 1, 161-162, (1974) · Zbl 0276.60005
[14] Karp, R.M; Pippenger, N, A time-randomness tradeoff, ()
[15] Karp, R.M; Upfal, E; Wigderson, A, The complexity of parallel computation on matroids, (), 541-550
[16] Karp, R.M; Wigderson, A, A fast parallel algorithm for the maximal independent set problem, (), 266-272
[17] Lubotzky, A; Phillips, R; Sarnak, P, Explicit expanders and the Ramanujan conjectures, (), 240-246
[18] Luby, M, A simple parallel algorithm for the maximal independent set problem, (), 1-10
[19] Shamir, A, How to share a secret, Comm. ACM, 22, 11, 612-613, (1979) · Zbl 0414.94021
[20] Sipser, M, A complexity theoretic approach to randomness, (), 330-335
[21] Spencer, T, Provably good pattern generators for random pattern test, (), 107-120
[22] Stockmeyer, L, The complexity of approximate counting, (), 118-126
[23] Yao, A.C, Theory and applications of trapdoor functions, (), 80-91
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.