×

zbMATH — the first resource for mathematics

Randomness in interactive proofs. (English) Zbl 0802.68053
Summary: The paper initiates a study of the quantitative aspects of randomness in interactive proofs. Our main result, which applies to the equivalent form of IP known as Arthur-Merlin (AM) games, is a randomness-efficient technique for decreasing the error probability. Given an AM proof system for \(L\) which achieves error probability 1/3 at the cost of Arthur sending \(l(n)\) random bits per round, and given a polynomial \(k = k(n)\), we show how to construct an AM proof system for \(L\) which, in the same number of rounds as the original proof system, achieves error \(2^{- k(n)}\) at the cost of Arthur sending only \(O(l+k)\) random bits per round.
Underlying the transformation is a novel sampling method for approximating the average value of an arbitrary function \(f:\{0,1\}^ l \to [0,1]\). The method evaluates the function on \(O(\varepsilon^{-2} \log \delta^{-1})\) sample points generated using only \(O(l + \log \delta^{-1})\) coin tosses to get an estimate which with probability at least \(1-\delta\) is within \(\varepsilon\) of the average value of the function.

MSC:
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
91A05 2-person games
94A60 Cryptography
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] L. Adleman. Two Theorems on Random Polynomial Time.Proceedings of the 19th Annual IEEE Symposium on the Foundations of Computer Science, IEEE (1978).
[2] W. Aiello, S. Goldwasser andJ. H?stad. On the Power of Interaction.Combinatorica 10(1) (1990), 3-25. · Zbl 0715.68028
[3] M. Ajtai, J. Komlos and E. Szemeredi. Deterministic Simulation in Logspace.Proceedings of the 19th Annual ACM Symposium on the Theory of Computing, ACM (1987). · Zbl 0489.05052
[4] N. Alon. Eigenvalues and Expanders.Combinatorica 6(2) (1986), 83-96. · Zbl 0661.05053
[5] L. Babai. Trading Group Theory for Randomness.Proceedings of the 17th Annual ACM Symposium on the Theory of Computing, ACM (1985).
[6] L. Babai andS. Moran. Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes.J. Computer and System Sciences 36 (1988), 254-276. · Zbl 0652.03029
[7] L. Babai andS. Moran. Proving Properties of Interactive Profs by a Generalized Counting Technique.Information and Computation 82 (1989), 185-197. · Zbl 0684.68068
[8] M. Bellare. Interactive Proofs and Approximation: Reductions from Two Provers in one Round.Proceedings of the 2nd Israel Symposium on Theory and Computing Systems, IEEE (June 1993). Preliminary version:IBM Research Report RC 17969 (May 1992).
[9] M. Bellare and P. Rogaway. The Complexity of Approximating a Nonlinear program.Complexity in Numerical Optimization, Ed. P.M. Pardalos, World Scientific Press (1993). Preliminary version:IBM Research Report RC 17831 (March 1992).
[10] M. Bellare and J. Rompel. Randomness-Efficient Sampling of Arbitrary Functions.MIT LCS Tech. Memo. TM-433.
[11] M. Bellare and J. Rompel. Trading Interaction for Randomness: Speedup at Logarithmic Cost. Manuscript (1991). Presented at DIMACS Workshop on Structural Complexity and Cryptography, Rutgers 1990.
[12] M. Ben-Or, S. Goldwasser, J. Kilian and A. Wigderson. Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions.Proceedings of the 20th Annual ACM Symposium on the Theory of Computing, ACM (1988).
[13] C. Bennet andJ. Gill. Relative to a random OracleA, P A ? NP A ? coNP A , with probability 1.SIAM J on Computing 10 (1981), 96-113. · Zbl 0454.68030
[14] M. Blum andS. Micali. How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits.SIAM Journal on Computing 13 (4) (1984), 850-864. · Zbl 0547.68046
[15] R. Boppana, J. Hastad andS. Zachos. Does coNP have Short Interactive Proofs?Info. Processing Letters 25 (1987), 127-132. · Zbl 0653.68037
[16] R. Canetti, G. Even andO. Goldreich. Lower bounds for sampling algorithms for estimating the average. TR-686, Computer Science Dept., Technion, Haifa, Israel, August 1991. · Zbl 0875.68529
[17] L. Carter andM. Wegman. Universal Classes of Hash Functions.J. Computer and System Sciences 18 (1979), 143-154. · Zbl 0412.68090
[18] B. Chor andO. Goldreich. On the Power of Two-Point Based Sampling.J. of Complexity 5 (1989), 96-106. · Zbl 0672.60105
[19] R. Chang, B. Chor, O. Goldreich, J. Hartmanis, J. H?stad, D. Ranjan, and P. Rohatgi. The Random Oracle Hypothesis is False. Submitted toJCSS. · Zbl 0813.68100
[20] A. Cohen and A. Wigderson. Dispersers, Deterministic Amplification, and Weak Random Sources.Proceedings of the 30th Annual IEEE Symposium on the Foundations of Computer Science, IEEE (1989).
[21] S. Cook. The Complexity of Theorem Proving Procedures.Proceedings of the 3rd Annual ACM Symposium on the Theory of Computing, ACM (1971). · Zbl 0253.68020
[22] U. Feige and L. Lov?sz. Two-Prover One Round Proof Systems: Their Power and their Problems.Proceedings of the 24th Annual ACM Symposium on the Theory of Computing, ACM (1992).
[23] O. Gabber andZ. Galil. Explicit Construction of Linear Sized Superconcentrators.J. Computer and System Sciences 22 (1981), 407-420. · Zbl 0487.05045
[24] O. Goldreich, R. Impagliazzo, L. Levin, R. Venkatesan and D. Zuckermann. Security Preserving Amplification of Hardness.Proceedings of the 31st Annual IEEE Symposium on the Foundations of Computer Science, IEEE (1990).
[25] O. Goldreich and L. Levin. A Hard-Core Predicate for any One-Way Function.Proceedings of the 21st Annual ACM Symposium on the Theory of Computing, ACM (1989).
[26] O. Goldreich, S. Micali andA. Wigderson. Proofs that Yield Nothing but their Validity or All Languages in NP have Zero-Knowledge Proof Systems.Journal of the ACM 38(1) (1991), 691-729. · Zbl 0799.68101
[27] S. Goldwasser, S. Micali andC. Rackoff. The Knowledge Complexity of Interactive Proofs.SIAM J. Computing 18 (1) (1989), 186-208. · Zbl 0677.68062
[28] S. Goldwasser and M. Sipser. Private Coins versus Public Coins in Interactive Proof Systems.Proceedings of the 18th Annual ACM Symposium on the Theory of Computing, ACM (1986).
[29] J. Hartmanis, R. Chang, D. Ranjan and P. Rohatgi. Structural Complexity Theory: Recent Surprizes.Technical Report 90-1117, Dept. of Computer Science, Cornell University (April 1990).
[30] J. H?stad. Pseudo-random generators under Uniform Assumptions.Proceedings of the 22nd Annual ACM Symposium on the Theory of Computing, ACM (1990).
[31] R. Impagliazzo. Private communication (December 1990).
[32] R. Impagliazzo, L. Levin and M. Luby. Pseudo-Random Generation from One-Way Function.Proceedings of the 21st Annual ACM Symposium on the Theory of Computing, ACM (1989).
[33] R. Impagliazzo and D. Zuckerman. How to Recycle Random Bits.Proceedings of the 30th Annual IEEE Symposium on the Foundations of Computer Science, IEEE (1989).
[34] R. Karp, N. Pippinger and M. Sipser. A Time-Randomness Tradeoff. In AMS Conference on Probabilistic Computational Complexity, Durham, New Hampshire (1985).
[35] A. Lubotzky, R. Phillips and P. Sarnak. Explicit Expanders and the Ramanujan Conjectures.Proceedings of the 18th Annual ACM Symposium on the Theory of Computing, ACM (1986). · Zbl 0619.10052
[36] C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic Methods for Interactive Proof Systems.Proceedings of the 31st Annual IEEE Symposium on the Foundations of Computer Scienc, IEEE (1990). · Zbl 0799.68097
[37] C. Lund and M. Yannakakis. On the Hardness of Approximating Minimization Problems.Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, ACM (1993). · Zbl 1310.68094
[38] N. Nisan. Pseudorandom Generators for Space Bounded Computation.Proceedings of the 22nd Annual ACM Symposium on the Theory of Computing, ACM (1990). · Zbl 0759.68024
[39] N. Nisan and A. Wigderson. Hardness vs. Randomness.Proceedings of the 29th Annual IEEE Symposium on the Foundations of Computer Science, IEEE (1988).
[40] M. Santha. On Using Deterministic Functions to Reduce Randomness in Probabilistic Algorithms.Information and Computation 74(3) (1987), 241-249. · Zbl 0629.68047
[41] A. Schrift. Chapter 4 of Ph.D Thesis, Dept. of Applied Mathematics and Computer Science, Weizmann Institute.
[42] A. Shamir. IP=PSPACE.Proceedings of the 31st Annual IEEE Symposium on the Foundations of Computer Science, IEEE (1990).
[43] V. Shoup. New Algorithms for Finding Irreducible Polynomials over Finite Fields.Proceedings of the 29th Annual IEEE Symposium on the Foundations of Computer Science, IEEE (1988). · Zbl 0712.11077
[44] M. Sipser. Expanders, Randomness, or Time Versus Space.Structure in Complexity Theory (1986). · Zbl 0606.68042
[45] A. Yao. Theory and Applications of Trapdoor Function.Proceedings of the 23rd Annual IEEE Symposium on the Foundations of Computer Science, IEEE (1982).
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.