×

zbMATH — the first resource for mathematics

Simulating BPP using a general weak random source. (English) Zbl 0857.68121
Summary: We show how to simulate BPP and approximation algorithms in polynomial time using the output from a \(\delta\)-source. A \(\delta\)-source is a weak random source that is asked only once for \(R\) bits, and must output an \(R\)-bit string according to some distribution that places probability no more than \(2^{-\delta R}\) on any particular string. We also give an application to the unapproximability of MAX CLIQUE.

MSC:
68U20 Simulation (MSC2010)
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] N. Alon and V. D. Milman, {\(\lambda\)}1, Isoperimetric Inequalities for Graphs and Superconcentrators,J. Combin. Theory Ser. B, 38:73–88, 1985. · Zbl 0549.05051
[2] S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof Verification and Intractibility of Approximation Problems,Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992, pp. 14–23. · Zbl 0977.68539
[3] S. Arora and S. Safra, Approximating Clique is NP-Complete,Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992, pp. 2–13. · Zbl 0945.68516
[4] L. Babai, L. Fortnow, and C. Lund, Non-Deterministic Exponential Time has Two-Prover Interactive Protocols,Comput. Complexity, 1:16–25, 1991. · Zbl 0774.68041
[5] M. Bellare and M. Sudan, Improved Non-Approximability Results,Proceedings of the 26th ACM Symposium on Theory of Computing, 1994, pp. 184–193. · Zbl 1344.68094
[6] C. H. Bennett, G. Brassard, and J.-M. Robert, Privacy Amplification by Public Discussion,SIAM J. Comput., 17(2):210–229, 1988. · Zbl 0644.94010
[7] M. Ben-Or and N. Linial, Collective Coin Flipping Robust Voting Schemes and Minimal Banzhaf Values, inAdvances in Computing Research 5: Randomness and Computation, S. Micali, ed., JAI Press, Greenwich, CT, 1989, pp. 91–115.
[8] M. Blum, Independent Unbiased Coin Flips from a Correlated Biased Source: a Finite Markov Chain,Combinatorica, 6(2):97–108, 1986. · Zbl 0618.60063
[9] L. Carter and M. Wegman, Universal Classes of Hash Functions,J. Comp. Syst. Sci., 18(2): 143–154, 1979. · Zbl 0412.68090
[10] B. Chor and O. Goldreich, Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity,SIAM J. Comput., 17(2):230–261, 1988. · Zbl 0644.94008
[11] B. Chor and O. Goldreich, On the Power of Two-Point Based Sampling,J. Complexity, 5:96–106, 1989. · Zbl 0672.60105
[12] B. Chor, O. Goldreich, J. Hastad, J. Friedman, S. Rudich, and R. Smolensky, The Bit Extraction Problem ort-Resilient Functions,Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985, pp. 396–407.
[13] A. Cohen and A. Wigderson, Dispersers, Deterministic Amplification, and Weak Random Sources,Proceedings of the 30th Annual Symposium on Foundations of Computer Science, 1989, pp. 14–19.
[14] M. Dyer, A. Frieze, and R. Kannan, A Random Polynomial Time Algorithm for Approximating the Volume of a Convex Body,J. Assoc. Comput. Mach., 38:1–17, 1991. · Zbl 0799.68107
[15] P. Elias, The Efficient Construction of an Unbiased Random Sequence,Ann. Math. Statist., 43(3):865–870, 1972. · Zbl 0245.65003
[16] U. Feige, S. Goldwasser, L. Lovasz, S. Safra, and M. Szegedy, Approximating Clique is Almost NP-Complete,Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991, pp. 2–12.
[17] L. Fortnow, J. Rompel, and M. Sipser, On the Power of Multi-Prover Interactive Protocols,Theoret. Comput. Sci. A, 134:545–557, 1994. · Zbl 0938.68824
[18] J. Friedman and A. Wigderson, On the Second Eigenvalue of Hypergraphs, Technical Report CS-TR-232-89, Princeton University, 1989. · Zbl 0843.05075
[19] O. Gabber and Z. Galil, Explicit Constructions of Linear-Sized Supercomputers,J. Comput. System Sci., 22:407–420, 1981. · Zbl 0487.05045
[20] R. Impagliazzo, L. Levin, and M. Luby, Pseudo-Random Generation from One-Way Functions,Proceedings of the 21st ACM Symposium on Theory of Computing, 1989, pp. 12–24.
[21] R. Impagliazzo and D. Zuckerman, How To Recycle Random Bits,Proceedings of the 30th Annual Symposium on Foundations of Computer Science, 1989, pp. 248–253.
[22] R. M. Karp, Reducibility Among Combinatorial Problems, inComplexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds., Plenum, New York, 1972, pp. 85–103.
[23] D. Lichtenstein, N. Linial, and M. Saks, Some Extremal Problems Arising from Discrete Control Processes,Combinatorica, 9:269–287, 1989. · Zbl 0699.90110
[24] N. Linial, M. Luby, M. Saks, and D. Zuckerman, Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension,Proceedings of the 25th ACM Symposium on Theory of Computing, 1993, pp. 258–267. · Zbl 1310.68207
[25] N. Nisan and D. Zuckerman, Randomness Is Linear in Space,J. Comput. System Sci., 52(1):43–52, 1996. · Zbl 0846.68041
[26] M. O. Rabin, Probabilistic Algorithm for Testing Primality,J. Number Theory, 12:128–138, 1980. · Zbl 0426.10006
[27] A. Sahay and M. Sudan, personal communication.
[28] M. Saks, A. Srinivasan, and S. Zhou, Explicit Dispersers with Polylog Degree,Proceedings of the 27th ACM Symposium on Theory of Computing, 1995, to appear. · Zbl 0978.68555
[29] M. Santha, On Using Deterministic Functions in Probabilistic Algorithms,Inform. and Comput., 74(3):241–249, 1987. · Zbl 0629.68047
[30] M. Santha and U. Vazirani, Generating Quasi-Random Sequences from Slightly Random Sources,J. Comput. System Sci., 33:75–87, 1986. · Zbl 0612.94004
[31] M. Sipser, Expanders, Randomness, or Time Versus Space,J. Comput. System Sci., 36:379–383, 1988. · Zbl 0652.68050
[32] A. Srinivasan and D. Zuckerman, Computing with Very Weak Random Sources,Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 264–275.
[33] R. M. Tanner, Explicit Construction of Concentrators from GeneralizedN-gons,SIAM J. Algebraic Discrete Methods, 5:287–293, 1984. · Zbl 0554.05045
[34] U. Vazirani, Randomness, Adversaries and Computation, Ph.D. Thesis, University of California, Berkeley, 1986.
[35] U. Vazirani, Efficiency Considerations in Using Semi-Random Sources,Proceedings of the 19th ACM Symposium on Theory of Computing, 1987, pp. 160–168.
[36] U. Vazirani, Strong Communication Complexity or Generating Quasi-Random Sequences from Two Communicating Semi-Random Sources,Combinatorica, 7(4):375–392, 1987. · Zbl 0643.94002
[37] U. Vazirani and V. Vazirani, Random Polynomial Time is Equal to Semi-Random Polynomial Time,Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985, pp. 417–428.
[38] J. von Neumann,Various Techniques Used in Connection with Random Digits, Notes by G. E. Forsythe, National Bureau of Standards, Applied Math Series, Vol. 12, Pitman, Boston, MA, 1951, pp. 36–38. Reprinted inVon Neumann’s Collected Works, Vol. 5, Pergamon, New York, 1963, pp. 768–770.
[39] A. Wigderson and D. Zuckerman, Expanders that Beat the Eigenvalue Bound: Explicit Construction and Applications,Proceedings of the 25th ACM Symposium on Theory of Computing, 1993, pp. 245–251. · Zbl 1310.68168
[40] D. Zuckerman, General Weak Random Sources,Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990, pp. 534–543.
[41] D. Zuckerman, Simulating BPP Using a General Weak Random Source,Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991, pp. 79–89.
[42] D. Zuckerman, NP-Complete Problems Have a Version That’s Hard To Approximate,Proceedings of the 8th IEEE Conference on Structure in Complexity Theory, 1993, pp. 305–312.
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.