×

zbMATH — the first resource for mathematics

Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds. (English) Zbl 1230.68076
Summary: We show that if Arthur-Merlin protocols can be derandomized, then there is a language computable in deterministic exponential-time with access to an NP oracle that requires circuits of exponential size. More formally, if every promise problem in prAM, the class of promise problems that have Arthur-Merlin protocols, can be computed by a deterministic polynomial-time algorithm with access to an NP oracle, then there is a language in \(E^{\text{NP}}\) that requires circuits of size \(\Omega (2^{n }/n)\). The lower bound in the conclusion of our theorem suffices to construct pseudorandom generators with exponential stretch.
We also show that the same conclusion holds if the following two related problems can be computed in polynomial time with access to an NP-oracle: (i) approximately counting the number of accepted inputs of a circuit, up to multiplicative factors; and (ii) recognizing an approximate lower bound on the number of accepted inputs of a circuit, up to multiplicative factors.

MSC:
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] S. Aaronson, B. Aydınlıoglu, H. Buhrman, J. Hitchcock & D. van Melkebeek, ”A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games,” ECCC technical report. TR10-174, 2010.
[2] S. Arora, & B. Barak, ”Complexity Theory: A Modern Approach,” Cambridge University Press, 2009. · Zbl 1193.68112
[3] V. Arvind & P. Mukhopadhyay, ”Derandomizing the isolation lemma and lower bounds for circuit size,” in Proceedings of the 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and the 12th International Workshop on Randomization and Computation, ser. LNCS 5171, 2008, pp. 276–289. · Zbl 1159.68634
[4] A. Atserias, ”Distinguishing SAT from polynomial-size circuits, through black-box queries,” in Proceedings of the 21st Annual IEEE Conference on Computational Complexity, pp. 88–95, 2006.
[5] L. Babai, L. Fortnow, N. Nisan & A. Wigderson, ”BPP has subexponential simulation unless EXPTIME has publishable proofs,” Computational Complexity, vol. 3, pp. 307–318, 1993. · Zbl 0802.68054
[6] Babai L., . Moran S: ”Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes”. Journal of Computer and System Sciences 36, 254–276 (1988) · Zbl 0652.03029
[7] M. Blum & S. Micali, ”How to generate cryptographically strong sequences of pseudo-random bits,” SIAM Journal on Computing, vol. 13, no. 4, pp. 850864, 1984. · Zbl 0547.68046
[8] A. Bogdanov & L. Trevisan, ”On worst-case to average-case reductions for NP problems,”SIAM Journal on Computing, vol. 36, no. 4, pp. 1119–1159, 2006. · Zbl 1118.68072
[9] Bshouty N.H., Cleve R., Gavaldà R., Kannan S. , Tamon C.: ”Oracles and queries that are sufficient for exact learning,”. Journal of Computer and System Sciences, 52(3), 421–433 (1996) · Zbl 0858.68075
[10] H. Buhrman, L. Fortnow & T. Thierauf, ”Nonrelativizing separations,” in Proceedings of the 13rd Annual IEEE Conference on Computational Complexity, 1998, pp. 8–12. · Zbl 0935.68032
[11] Cai J.-Y.: ” $${\(\backslash\)mathrm{S}_2\^p \(\backslash\)subseteq \(\backslash\)mathrm{ZPP}\^{\(\backslash\)mathrm{NP}}}$$ ,”. Journal of Computer and System Sciences 73(1), 25–35 (2007) · Zbl 1133.68020
[12] V. T. Chakaravarthy & S. Roy, ”Finding irrefutable certificates for $${S_2\^P}$$ via Arthur and Merlin,” in Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science, 2008, pp. 157–168. · Zbl 1259.68071
[13] Dvir Z., Shpilka A., Yehudanoff A.: ”Hardness-randomness tradeoffs for bounded depth arithmetic circuits,”. SIAM Journal on Computing 39(4), 1279–1293 (2009) · Zbl 1205.68170
[14] Even S., Selman A.L., Yacobi Y.: ”The complexity of promise problems with applications to public-key cryptography,”. Information and Control 61(2), 159–173 (1984) · Zbl 0592.94012
[15] Fortnow L., Pavan A., Sengupta S.: ”Proving SAT does not have small circuits with an application to the two queries problem,”. Journal of Computer and System Sciences 74(3), 358–363 (2008) · Zbl 1135.68022
[16] M. Fürer, O. Goldreich, Y. Mansour, M. Sipser & S. Zachos, ”On completeness and soundness in interactive proof systems,” Advances in Computing Research 5: Randomness and Computation, pp. 429–442, 1989.
[17] O. Goldreich, ”On promise problems (a survey in memory of Shimon Even [1935-2004]),” ECCC technical report. TR05-018, 2005.
[18] O. Goldreich, ”Computational Complexity: A Conceptual Perspective,” Cambridge University Press, 2008. · Zbl 1154.68056
[19] O. Goldreich, ”In a world of P=BPP,” ECCC technical report. TR10-135, 2010.
[20] Goldwasser S., Micali S., Rackoff C.: ”The knowledge complexity of interactive proof systems,”. SIAM Journal on Computing 18(1), 186–208 (1989) · Zbl 0677.68062
[21] S. Goldwasser & M. Sipser, ”Private coins versus public coins in interactive proof system,” in Advances in Computing Research, Vol. 5: Randomness and Computation, S. Micali, Ed. JAI Press, 1989, pp. 73–90.
[22] D. Gutfreund & A. Kawachi, ”Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds,” in Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010, pp. 38–49.
[23] Impagliazzo R., Kabanets V., Wigderson A.: ”In search of an easy witness: exponential time vs. probabilistic polynomial time,”. Journal of Computer and System Sciences 65(4), 672–694 (2002) · Zbl 1059.68047
[24] R. Impagliazzo & A. Wigderson, ”P=BPP if E requires exponential circuits: Derandomizing the XOR lemma,” in Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997, pp. 220–229. · Zbl 0962.68058
[25] Kabanets V., Impagliazzo R.: ”Derandomizing polynomial identity tests means proving circuit lower bounds,”. Computational Complexity 13(1-2), 1–46 (2004) · Zbl 1089.68042
[26] Kannan R.: ”Circuit-size lower bound and non-reducibility to sparse sets,”. Information and Control 55(1–3), 40–56 (1982) · Zbl 0537.94027
[27] R. M. Karp & R. J. Lipton, ”Some connections between nonuniform and uniform complexity classes,” in Proceedings of the 12th Annual Symposium on Theoretical Computer Science, 1980, pp. 302–309.
[28] J. Kinne, D. van Melkebeek & R. Shaltiel, ”Pseudorandom generators and typically-correct derandomization,” in Proceedings of the 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and the 13th International Workshop on Randomization and Computation, 2009, pp. 574–587. · Zbl 1255.68292
[29] Klivans A.R., van Melkebeek D.: ”Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses,”. SIAM Journal on Computing 31(5), 1501–1526 (2002) · Zbl 1016.68060
[30] Miltersen P.B., Vinodchandran N.V.: ”Derandomizing Arthur-Merlin games using hitting sets,”. Computational Complexity 14(3), 256–279 (2005) · Zbl 1085.68058
[31] P. B. Miltersen, N. V. Vinodchandran & O. Watanabe, ”Super-polynomial versus half-exponential circuit size in the exponential hierarchy,” in Proceedings of the 5th Annual International Conference on Computing and Combinatorics, 1999, pp. 210–220. · Zbl 0944.68074
[32] Nisan N.: ”Pseudorandom bits for constant depth circuits,”. Combinatorica 11, 63–70 (1991) · Zbl 0732.68056
[33] Nisan N., Wigderson A.: ”Hardness vs. randomness,”. Journal of Computer and System Sciences 49, 149–167 (1994) · Zbl 0821.68057
[34] R. Santhanam, ”Circuit lower bounds for Merlin-Arthur classes,” in Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007, pp. 275–283. · Zbl 1232.68058
[35] R. Shaltiel & C. Umans, ”Simple extractors for all min-entropies and a new pseudo-random generator,” Journal of ACM, vol. 52, no. 2, pp. 172–216, 2005. · Zbl 1317.68132
[36] Shaltiel R., Umans C.: ”Pseudorandomness for approximate counting and sampling,”. Computational Complexity 15(4), 298–341 (2006) · Zbl 1125.68058
[37] Shannon C.E.: ”The synthesis of two-terminal switching circuits,”. Bell System Technical Journal 28(1), 59–98 (1949)
[38] Umans C.: ”Pseudo-random generators for all hardnesses,”. Journal of Computer and System Sciences 67(2), 419–440 (2003) · Zbl 1072.68129
[39] Viola E.: ”Pseudorandom bits for constant-depth circuits with few arbitrary symmetric gates,”. SIAM Journal on Computing 36(5), 1387–1403 (2007) · Zbl 1124.68037
[40] A. C. Yao, ”Theory and application of trapdoor functions,”in Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982, pp. 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.