Regular PapersNo Access

NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES

N. V. VINODCHANDRAN

Department of Computer Science and Engineering, University of Nebraska-Lincoln, USA

https://doi.org/10.1142/S0129054105003819Cited by:3 (Source: Crossref)

Abstract

We investigate the complexity of strong nondeterministic circuit minimization problem (SNCMP in short) in relation to derandomizing Arthur-Merlin games. We show derandomization results for Arthur-Merlin games under both easiness and hardness assumptions about the complexity of SNCMP. Assuming SNCMP is non-uniformly easy, we present derandomization of Arthur-Merlin games using weaker hardness assumptions than what is currently known. On the other hand, we show that establishing SNCMP is hard for SAT or Graph Isomorphism problem under certain natural reductions will show that Graph Nonisomorphism problem has subexponential proofs of membership. We combine known constructions of pseudorandom and hitting set generators to prove our results.

Keywords:

AMSC: 68Q15

References

E. Allenderet al., Derandomization and distinguishing complexity, Proceedings of the 18th Annual IEEE Conference on Computational Complexity (2003) pp. 209–220. Google Scholar
V. Arvindet al., Theoretical Computer Science 137(2), 279 (1995). Crossref, Web of Science, Google Scholar
V. Arvind and Johannes Köbler, Theoretical Computer Science 255(1–2), 205 (2001). Crossref, Web of Science, Google Scholar
L. Babai, Trading group theory for randomness, Proceedings of the 17th ACM Symposium on Theory of Computing (1985) pp. 421–429. Google Scholar
L. Babaiet al., Computational Complexity 3(4), 307 (1993). Crossref, Google Scholar
L. Babai and S. Moran, Journal of Computer and System Sciences 36, 254 (1988). Crossref, Web of Science, Google Scholar
J. Balcázar , J. Díaz and J. Gabarró , Structural Complexity – I & II ( Springer Verlag , 1988 ) . Crossref, Google Scholar
M. Blum and S. Micali, SIAM Journal on Computing 13(4), 850 (1984). Crossref, Web of Science, Google Scholar
O. Goldreich and L. Levin, A hard-core predicate for all one-way functions, Proceedings of the 21th Annual ACM Symposium on Theory of Computing (1989) pp. 25–32. Google Scholar
O. Goldreich, S. Micali and A. Wigderson, Journal of the Association for Computing Machinery 38(3), 691 (1991). Web of Science, Google Scholar
O. Goldreich and D. Zuckerman. Another proof that BPP⊆PH (and more). Technical Report 45, Electronic Colloquium on Computational Complexity, 1997 . Google Scholar
S. Goldwasser and M. Sipser, Advances in Computing Research 5, 73 (1989). Google Scholar
D. Gutfreund, R. Shaltiel and A. Ta-Shma, Computational Complexity 12, 85 (2003). Web of Science, Google Scholar
R. Impagliazzo, Hard-core distributions for somewhat hard problems, Proceedings of the 36th IEEE Annual Symposium on Foundations of Computer Science (1995) pp. 538–547. Google Scholar
R. Impagliazzo, V. Kabanets and A. Wigderson, Journal of Computer and System Sciences 65, 672 (2002). Crossref, Web of Science, Google Scholar
R. Impagliazzo and A. Wigderson, P=BPP if E requires exponential circuits: Derandomizing the XOR lemma, Proceedings of the 29th Annual ACM Symposium on Theory of Computing (1997) pp. 220–229. Google Scholar
V. Kabanets, Journal of Computer and System Sciences 63(2), 236 (2001). Crossref, Web of Science, Google Scholar
V. Kabanets and J.-Y. Cai, Circuit minimization problem, Proceedings of the 32nd ACM Symposium on Theory of Computing (2000) pp. 73–79. Google Scholar
A. Klivans and D. van Melkebeek, SIAM Journal on Computing 31, 1501 (2002). Crossref, Web of Science, Google Scholar
Chi-Jen Lu, Computational Complexity 10, 247 (2001). Crossref, Web of Science, Google Scholar
P. B. Miltersen and N. V. Vinodchandran, Derandomizing Arthur-Merlin games using hitting sets, Proceedings of the 40th Annual Symposium on Foundations of Computer Science (1999) pp. 71–80. Google Scholar
N. Nisan and A. Wigderson, Journal of Computer and System Sciences 49(2), 149 (1994). Crossref, Web of Science, Google Scholar
C. Papadimitriou , Computational Complexity ( Addison-Wesley , 1994 ) . Google Scholar
R. Shalitiel and C. Umans, Simple extractors for all minentropies and a new pseudorandom generator, Proceeding of the 41st IEEE Symposium on Foundations of Computer Science (2001) pp. 648–657. Google Scholar
R. Shaltiel and C. Umans. Pseudorandomness for approximate counting and sampling. Technical Report TR04-84, Electronic Colloquium on Computational Complexity, 2004. Available at http://www.eccc.uni-trier.de/eccc . Google Scholar
A. C. Yao, Theory and application of trapdoor functions, Proceedings of 23rd IEEE Symposium on Foundations of Computer Science (1982) pp. 80–91. Google Scholar